对数函数的渐近复杂性

Question

我知道，就复杂性而言，O(logn)比O(n)快，O(Logn)比O(nlogn)快，O(n2)快。但是关于O(n2)和O(n2log)，或者O(n2.001)和O(n2log)：

T1(n)=n^2 + n^2logn

这个功能的大欧和欧米茄是什么？还有，什么是小哦？相对于：

T2(n)=n^2.001 + n^2logn

现在大欧有什么区别吗？我很难理解如何将logn与n的幂进行比较。例如，logn大约是n^0.000000.1还是n^1.000000.1？

Answer 1

T(n)=n^2 + n^2logn 这个功能的大欧和欧米茄是什么？还有，什么是小哦？

引用先前的回答：

不要忘记大O表示法代表一个集合。O(g(n))是所有函数f的集合，使得f没有比g增长得更快，形式上也是一样的，即存在着C和n0，因此我们对每个n >= n0都有|f(n)| <= C|g(n)|。表达式f(n) = O(g(n))是表示f(n)在集合O(g(n))中的缩写。

此外，您还可以将大O看作≤，而小O可以看作是< (reference)。所以你更关心的是找到相关的大o约束，而不是小O。在你的例子中，使用大θ甚至是合适的，即=。既然n^2 log n主宰了n^2，那么

T1(n)=n^2 + n^2logn = Ө(n^2 logn)

现在是第二部分。log n增长如此缓慢，甚至连n^e, e > 0也主宰了它。有趣的是，您甚至可以证明lim n^e/(logn)^k=inf作为n走向无穷大。由此可以看出，n^0.001在log n中占据主导地位

T2(n)=n^2.001 + n^2logn = Ө(n^2.001).

如果是f(n) = Ө(g(n))，那么f(n) = O(g(n))回答你的问题也是真的：

• T1(n)=O(n^2 logn)
• T2(n)=O(n^2.001)