对数与幂的渐近复杂性
对数与幂的渐近复杂性
提问于 2013-04-10 01:53:15
嘿，伙计们，我正在从Dasgupta的算法书中解决一些大问题，并且被困在一些问题上。
1) f(n) =n^0.1g(N)= (log )^10
根据Asymptotic Complexity of Logarithms and Powers上的最高答案，“对于任何正数a，b，log(N)^a总是O(n^b)。”所以对于1)，f= omega(g)
2) f(n) =n^1.01g(N)=nlog^2n我猜f= omega(g)。这个例子是正确的还是不同的情况，因为log是平方并乘以n？
请说明您为解决这类问题而采取的步骤
Stack Overflow用户
发布于 2013-08-22 01:38:08
你对第一个问题的回答是正确的，你对该规则的应用也是正确的。这里有一个证明，对于任何a>0，log(n) = O(n^a) (显然与上述规则等价)：
The derivative of n^a is a*(n^(a-1))
The derivative of log(n) = 1/n
Therefore, for large enough n, the derivative of n^a is more than the derivative of log(n)
Therefore, for large enough n, n^a > log(n)
Therefore log(n) = O(n^a)你对第二个问题的回答是正确的。这是一个证据：
g(n) = O(f(n)) if and only if log(log(n)) = O(n^0.01)
log(log(n)) = O(log(n)) so log(log(n)) = O(O(n^0.01)) = O(n^0.01)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15909068
复制相关文章
相似问题
腾讯云开发者
