1

次のステートメントのいくつかを証明する方法を完全に理解するのに問題があります。

たとえば、次のステートメントがありますn^2logn = O(n^2)。私が間違っている場合は訂正しn^2てbigOくださいn^2logn。n^2よりも速く成長することを意味しn^2lognます。では、これを証明するにはどうすればよいでしょうか。私は、使用しようとしたがその過程で立ち往生した帰納法による証明を使用する必要があると思います。このステートメントを次のように書き直してもらえn^2logn <= n^2ますか?

帰納法を使って何かを反証することは可能ですか? たとえば、反証n!=O(n^n)。それとも、任意の値 (2 より大きいとしましょう) がステートメントを満たさないことを単に示すことによって、ステートメントを反証することは有効ですか?

そして最後に、明確にするために、bigTheta は、正しく成長する場合、方程式は同等であると述べていますか?

4

2 に答える 2

6

この主張n^2lognは、O(n^2)n^2logn が最大で漸近的に増加することを直感的に意味していn^2ます (この主張は間違っています)。

定義により、これは、 for each のようないくつかの定数 c,N があることを意味しますn>N。c*n^2logn <= n^2

それを反証することは、矛盾によって非常に簡単です。
(誤って) 主張が真であると仮定しN,c、定数を次のようにします。

c*n^2logn <= n^2
c*logn <= 1
logn <= 1/c

しかしc、一定であり、そのn>Nようなものもありlogn > 1/cます-矛盾。

他の何かを示すことで、誘導によって反証することができますn! < n^n。n! = n^n

ビッグ シータについては、スレッドBig Theta Notation でこの問題を詳しく説明しようとしましたが、ビッグ シータは正確には何を表しているのでしょうか?

于 2014-02-06T20:52:03.763 に答える