1

ビッグ シータ、ビッグ オー、ビッグ オメガの概念を理解しています。それを証明するのに苦労しています。誘導を行ってから長い時間が経ったので、さびて単純なものが欠けているだけだと確信しています。

たとえば..私が助けを必要としている問題は、それを示すこと5n² - 6n = Θ(n²)です。

問題の Big-Oh 部分を取得しました (big-Oh と Ω を別々に修正しますか?)。

6k² >= 5n² - 6n

そして大きなオメガ部分は：

5n² - 6n >= n²

....しかし、ここからどこへ行くのですか?! 私は誘導から何かを思い出します... 私はこれらが真実であると仮定します.そして今(n+1)、それぞれnにプラグインして..何かをしますか？この時点で私は自分を見失いました。

4

1 に答える 1

1

5n ^ 2-6nがO（n ^ 2）であることを示すには、すべての数n> = n0に対して、ある数n0および定数cに対して5n ^ 2-6n <= cn^2であるというステートメントを証明する必要があります。

帰納法による証明には、基本ケースの主張を証明し、帰納法のステップを証明することが含まれます。この例では、n = 1の場合の基本ケースが、ある定数cに対して明らかに当てはまることがわかります。

誘導ステップでは、ある数kについて主張が真であると仮定し、それを使用して、主張がk+1に対して真であることを示します。したがって、5k ^ 2-6k <= ck ^ 2と仮定し、次のように表示します。

5(k+1)^2 - 6(k+1)  = 5k^2 +10k + 5 -6k - 6
                   = 5k^2-6k + 10k -1        
                  <= ck^2 + 10k - 1
                  <= ck^2 + c*2k + c       (for any constant c  >= 5)
                   = c(k+1)^2

これにより、k + 1の主張が証明され、証明が完成します。

同様の方法で、オメガの大きな主張を証明することができます。

于 2012-09-19T16:43:40.723 に答える