如果 f(n)=O(g(n))，那么 f(n)∗log2(f(n)^c)=O(g(n)∗log2(g(n))) 不应该取决于 C 的值吗？

Question

如果 f(n)=O(g(n))，那么应该不应该依赖于常数C呢？f(n)∗log2(f(n)^c)=O(g(n)∗log2(g(n))) 这里C是一个正常数。根据我的理解，如果C很大，那么该语句将变为假，如果c很小，则为真。因此，结果取决于c。

我正在上算法课，这是我被问到的问题之一。根据我的理解，这应该依赖于常数c，但答案是错误的。

- Charu

Answer 1

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)))

- Mitch Wheat

---

我可以看到左右两边有相似的视图，但是f和g是不同的函数，那么为什么要...f... = O (...g...)呢？ - Undefitied

Answer 2

根据大O符号的定义，当且仅当存在常量“c”和N，使得对于所有n > N，f(n) <= c * g(n)，则有 f(n) = O(g(n))。 当我们断言f(n)“等于”O(g(n))时，我们并不是说它们在代数术语上必须“相等”。我们是说f(n)被g(n)上界限制。如果f和g是非递减的，并且总是大于1，而且c是一个正常量，那么Mitch Wheat给出的证明是正确的。

- Ryan E Washburn

Answer 3

解决左侧问题，

= f(n) * log2(f(n)^c)
= f(n) * c * log2(f(n)

现在既然f(n) = O(g(n))恰好相等。 我们可以写成,

= c * g(n) * log2(g(n))

在对上述语句进行大O符号表示后，

= c * O(g(n)*log2(g(n))
= O(g(n)*log2(g(n))

现在尝试在绘图计算器或Desmos上绘制xlog2(x) * constant，对于正的y = x或简单的x值，你会发现当你试图增加常数c的值时，图形不会改变。你还可以通过“大O符号”的定义来证明这一点。

- 101

Answer 4

假设：

1. f和g是正整数上的非递减实值函数，且n≥2
2. f(n) = O(g(n)), g(n) <= c1 f(n) and log (g(n)) <= log (c2 f(n))
利用1和2，我们知道g(n)受到c f(n)的限制，而f和g是非递减函数，如下所推导。

利用1和2，从g(n) * log2 (g(n))开始。

g(n) * log2 (g(n)) <= c1 f(n) * log2 (c2*f(n))
g(n) * log2 (g(n)) <= c1 f(n) * (log2 c2 + log2 f(n))
g(n) * log2 (g(n)) <= c1 f(n) * log2 c2 + c1 f(n) * log2 f(n)
g(n) * log2 (g(n)) <= c1 * log2 c2 * f(n) + c1 f(n) * log2 f(n) <= c1 * log2 c2 * f(n) * log2 f(n)
g(n) * log2 (g(n)) <= c * f(n) * log2 f(n)
g(n) * log2 (g(n)) <= O(f(n) * log2 f(n))
QED

- vCillusion