O(nlogn) も O(n^2) であるというのは本当ですか、また、omega(nlogn) も omega(n^2) であるというのは誤りですか?
user1941394
質問する
49 次
3 に答える
0
漸近表記については、他の回答を参照してください。答えはイエスですがΟ(nlg(n))⊂Ο(n^2)、その逆ではありません（Ο(n^2)⊄Ο(nlg(n))）
f(x) ∈ Ο(nlg(n))lim(x->inf) (f(x)/Ο(nlg(n)))const（0の場合もあります）であると述べます。小さなオメガ表記の場合、それは無限大f(x) ∈ ω(nlg(n))であることを意味します。lim(x->inf) (f(x)/ω(nlg(n)))（ωは下限と呼ばれます）だからあなたは正しいです、ω(nlg(n))⊄ω(n^2)
于 2013-01-13T20:32:56.480 に答える
0
O(n log n)より小さいO(n ^ 2): それらを割ると、 のn log n / n ^ 2 = log n / n = 0場合n -> infinity。それらの比率は 1 ではなく 0 に収束するため、同等の複雑度ではありません。
于 2013-01-13T20:15:52.157 に答える
0
Ο は、同等の制限動作を持つ関数のクラスです。関数g ( n ) ∈ Ο( f ( n )) は、n ⟶ ∞ の場合、fはgより大幅に速く成長しないことを意味します。
この点で、f( n ) = n · log n ∈ Ο( n 2 ) のステートメントは、 n · log nがn 2より大幅に速く成長しないため、真です。
ただし、一般的に、これらの表記は最も近い境界を表すために使用されます。したがって、関数が Ο( n ·log n ) にある場合、その制限動作を説明するために Ο( n 2 ) を使用しません。
于 2013-01-13T20:30:09.447 に答える