如何证明这一点？

Question

假设f(n) ∈ O(log2(n))。我们可以说 2^f(n) ∈ O(n) 吗？ 我可能让自己感到困惑，但从数学上讲这不是真的吗？因为 2^log2(n) 是 n，而 n 就复杂度而言是 O(n) 的一个元素？但是，我如何证明这一点？

Answer 1

不，这不是真的。您可以转换为

2^f(n) = n^O(1)

as f(n) < c*log2(n)（对于大n）仅意味着

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

有一些未公开的常量 c。