f(n)/log(n) = O( g(n) )⇒g(N)=Θ(f(n))？

Question

有没有可能证明，f(n)/log(n) = O(g(n)) => g(n) = Θ(f(n))

现在我站在这里

1. f(n)/log(n) = O(g(n)) ⇒ f(n)/log(n) ≤ c₁⋅g(n) ⇒ f(n)/(c₁⋅log(n)) ≤ g(n)
2. g(n) = Θ(f(n)) ⇒ c₂⋅f(n) ≤ g(n) ≤ c₃⋅f(n)

然后我说：c₂ = 1/(c₁⋅log(n)) ⇒ c₂⋅f(n) ≤ g(n)

如果是对的，我该如何显示上限呢？

Answer 1

不，这不是真的。有两个问题。首先，Theta关系涉及上界和下界，但是(正如您注意到的)您只假定g给出了f的上界。例如，尝试f(n) =0和g(n) = n:假设是正确的，但结论是假的。其次，log(n)的因子不是常数，这也将阻止您在f和g之间建立紧密的连接；例如，请参见@templatetypedef中的注释。

Answer 2

如前所述，您可以使用一个(泛型)示例来验证该假设：

让f(n) = g(n) ⋅ log(n)，然后f(n)/log(n) ∈ O(g(n))保持，但显然g(n) ∉ Θ(f(n))。

你能展示的是：

f(n)/h(n) ∈ Θ(g(n))   ⇒   g(n) ∈ Θ(f(n)/h(n))   ⇒   g(n) ∈ O(f(n))