对数函数的渐近复杂性

Question

我知道在复杂性方面,O(logn)比O(n)快,后者比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的幂进行比较.如在,登录大约n ^ 0.000000 ... 1或n ^ 1.000000 ... 1？

Answer 1

O(n^k)O(n^k')比所有人都快k, k' >= 0并且k' > k

O(n^2)会比O(n^2*logn)

请注意，您只能忽略常量，任何涉及输入大小的内容都不能被忽略。

因此， 的复杂度T(n)=n^2 + n^2logn将是两者中最差的，即O(n^2logn)。

小哦

宽松地说，“小哦”是有保证的上限。是的，这叫小，而且限制比较多。

n^2 = O(n^k)对于k >= 2但n^2 = o(n^k)对于k > 2

实际上，它是Big-Oh最受关注的。

关于什么T(n)= n^2.001 + n^2logn？

我们有 n ^2.001 = n ² *n ^0.001和 n ² * log(n)。

为了解决这个问题，我们需要找出最终哪个会更大，n ^0.001或 log(n)。

事实证明， n ^k with形式的函数k > 0最终将取代log(n)足够大的n。

这里的情况也是如此，因此T(n) = O(n ^2.001) .

但实际上，log(n)将大于 n ^0.001。

(10 ³³⁰⁰ ) ^0.001 < log(10 ³³⁰⁰ ) (1995.6 < 3300)，在这种情况下足够大的 n大约为 10 ³⁶⁵⁰，这是一个天文数字。

值得再次提及的是，10 ³⁶⁵⁰。宇宙中有10 ^{82个原子。}