algorithm - 对数的复杂度分析

Question

我有两个函数，f(n)=log ₂ n 和 g(n)=log ₁₀ n。我试图确定 f(n) 是 O(g(n))，还是 Ω(g(n)) 或 Θ(g(n))。我认为我应该取极限 f(n)/g(n)，因为 n 趋于无穷大，我认为极限是常数，所以 f(n) 必须是 Θ(n)。

我对吗？

Answer 1

log ₂ n = log ₁₀ n / log ₁₀ 2（从这里）

所以 f(n) = g(n) / log ₁₀ 2

因此 f(n) 和 g(n) 仅相差一个常数因子（因为 log ₁₀ 2 是常数）。

因此，根据O(x)、Ω(x) 和 Θ(x) 的定义，我想说：

f(n) ∈ O(g(n)),
f(n) ∈ Ω(g(n)),
f(n) ∈ Θ(g(n))

Answer 2

是的你是对的。从复杂性的角度来看（至少从大 O 的角度来看）它是 log ₂还是 log ₁₀并不重要。

f(n) 是 O(g(n)) 并且 f(n) 是 Ω(g(n))，f(n) 是 Θ(g(n))

Answer 3

由于限制是恒定的，因此 f(n) ∈ Θ(g(n)) 是正确的（假设您在问题中有错字）。当然还有 g(n) ∈ Θ(f(n))。

顺便说一句：不仅比率的限制是常数，而且 log ₂ n/log ₁₀ n 始终是常数（log ₂ 10）。