Cha*_*aru 9 asymptotic-complexity
如果f(n)=O(g(n)),那么不应该f(n)?log2(f(n)^c)=O(g(n)?log2(g(n)))依赖于C的值？
这里C是正常数.根据我的说法,如果C很大,那么声明将变为假,如果c很小,那么它就是真的.因此结果取决于c.
我正在上课算法,这是我被问到的问题之一.据我说,这应该依赖于常数c,但答案是错误的.
Mit*_*eat 20
log(x^c) = c * log(x)
所以,
log2(f(n)^c) == c * log2(f(n))
因此,
f(n)?log2(f(n)^c) = c * f(n) * log2(f(n))
= O(g(n)?log2(g(n)))