如果f(n)=O(g(n))，那么不应该f(n)∗log2(f(n)^c)=O(g(n)∗log2(g(n)))取决于 C 的值吗？
这里 C 是一个正常数。根据我的说法，如果 C 很大，那么该陈述将变为错误，如果 c 很小，则该陈述将是真实的。因此结果取决于c。
我正在上一门算法课，这是我被问到的问题之一。根据我的说法，这应该取决于常数 c 但答案是错误的。
问问题
11282 次
2 回答
23
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)))
于 2013-01-30T06:40:56.580 回答
3
@Undefitied，根据 Big-Oh 符号的定义 f(n) = O(g(n)) 当且仅当存在一个常数“c”和一个 N 使得 f(n) <= c*f(n ) 对于所有 n > N。当我们断言 f(n) 与 O(g(n))“相等”时，我们并不是说它们在代数术语中必然“相等”。我们说 f(n) 以 g(n) 为界。如果 f 和 g 是不减的并且总是大于 1，并且 c 是一个正常数，那么 Mitch Wheat 上面给出的证明是正确的。
于 2021-04-08T14:04:40.117 回答