很明显，log(n) 是 O(n)。但是，(log(n))^2 呢？ sqrt(n) 或 log(n) - 什么是什么？
有这样一组比较:
nᵃ (vs.) (log(n))ᵇ
我经常遇到这些比较，但我从来没有想出解决它们的好方法。解决一般案例的策略提示？
[编辑:我不是在谈论计算这些函数值的计算复杂性。我说的是功能本身。例如，f(n) = n 是 g(n) = log(n) 的上限，因为 f(n) ≤ c g(n) 用于 c = 1 和 n₀ > 0。]
最佳答案
对于任何正常数 a、b，log(n)^a 总是 O(n^b)。
您在寻找证据吗？所有这些问题都可以通过以下技巧简化为看到 log(n) 是 O(n):
log(n)^a = O(n^b) 等同于: log(n) = O(n^{b/a})，因为提高到 1/a 次方是递增函数。 这相当于 log(m^{a/b}) = O(m)，通过设置 m = n^{b/a}。 这相当于 log(m) = O(m)，因为 log(m^{a/b}) = (a/b)*log(m)。
您可以通过归纳法证明 log(n) = O(n)，重点关注 n 是 2 的幂的情况。
关于big-o - 对数和幂的渐近复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7882915/