O(nlogn) 也是 O(n^2) 是真的吗，omega(nlogn) 也是 omega(n^2) 也是假的吗谢谢
user1941394
问问题
49 次
3 回答
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 回答
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 回答