对数函数的渐近复杂性
我知道，就复杂性而言，O（logn）比O（n）快，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的幂进行比较。 如在中，logn近似为n ^ 0.000000 ... 1或n ^ 1.000000 ... 1？
对于所有k, k' >= 0 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 ？ 我们有n2.001 = n2 * n0.001和n2 * log（n）。
要解决这个问题，我们需要弄清楚什么最终会更大，n0.001或log（n）。
事实证明，具有k > 0的形式nk的函数最终将接管log(n)足够大的n 。
这里的情况也是如此，因此T(n) = O （n2.001 ) 。
实际上， log(n)将大于n0.001。
（103300）0.001 <log（103300） (1995.6 < 3300) ，并且在这种情况下足够大的n仅为103650左右，这是一个天文数字。
值得一提的是， 103650 。 宇宙中有1082个原子。
T(n)=n^2 + n^2logn
什么是这个功能的大哦和欧米茄？ 另外，什么是小哦？
引用以前的答案：
不要忘记大O符号代表一组。 O(g(n))是所有函数f的集合，使得f不会比g快，从形式上说，存在C和n0使得|f(n)| <= C|g(n)| |f(n)| <= C|g(n)| 对于每一个n >= n0 。 表达式f(n) = O(g(n))是f(n)在集合O(g(n))的简写
你也可以把大O看作≤和小O看作< （参考）。 所以你更关心的是找到相关的大O比小O更有效。 在你的情况下，甚至适用于使用=大theta。 由于n^2 log n支配n^2所以这是事实
T1(n)=n^2 + n^2logn = Ө(n^2 logn)
现在是第二部分。 log n增长得如此之慢以至于即使n^e, e > 0占主导地位。 有趣的是，当n变为无穷大时，甚至可以证明lim n^e/(logn)^k=inf 。 从这个角度来看，你有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)