问题描述
因此，很明显，log(n)是O(n).但是(log(n))^ 2呢? sqrt(n)或log(n)怎么办?什么限制了?
So, clearly, log(n) is O(n). But, what about (log(n))^2? What about sqrt(n) or log(n)--what bounds what?
有一系列这样的比较:
n ^ a与(log(n))^ b
There's a family of comparisons like this:
n^a versus (log(n))^b
我经常遇到这些比较，但我从来没有想出解决这些问题的好方法.是否有解决一般案件的策略提示?
I run into these comparisons a lot, and I've never come up with a good way to solve them. Hints for tactics for solving the general case?
谢谢，
伊恩
我不是在说计算这些函数的值的计算复杂性.我说的是功能本身.例如，f(n)= n是g(n)= log(n)的上限，因为对于c = 1和n0> 0，f(n)
I'm not talking about the computational complexity of calculating the values of these functions. I'm talking about the functions themselves. E.g., f(n)=n is an upper bound on g(n)=log(n) because f(n)<=c*g(n) for c=1 and n0 > 0.
推荐答案
log(n)^ a始终为O(n ^ b).
log(n)^a is always O(n^b), for any positive constants a, b.
您在寻找证明吗?通过以下技巧，可以将所有这些问题简化为看到log(n)为O(n):
Are you looking for a proof? All such problems can be reduced to seeing that log(n) is O(n), by the following trick:
log(n)^ a = O(n ^ b)等效于:log(n)= O(n ^ {b/a})，因为提高到1/a幂是一个递增函数.这相当于通过设置m = n ^ {b/a}，log(m ^ {a/b})= O(m).等效于log(m)= O(m)，因为log(m ^ {a/b})=(a/b)* log(m).
log(n)^a = O(n^b) is equivalent to:log(n) = O(n^{b/a}), since raising to the 1/a power is an increasing function.This is equivalent to log(m^{a/b}) = O(m), by setting m = n^{b/a}.This is equivalent to log(m) = O(m), since log(m^{a/b}) = (a/b)*log(m).
您可以通过归纳证明log(n)= O(n)，着眼于n是2的幂的情况.
You can prove that log(n) = O(n) by induction, focusing on the case where n is a power of 2.
这篇关于对数和幂的渐近复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！