<分区>
假设 f(n) ∈ O(log2(n))。我们可以说 2^f(n) ∈ O(n) 吗？ 我可能让自己感到困惑，但从数学上讲这不是真的吗？因为 2^log2(n) 是 n，而 n 就复杂度而言是 O(n) 的一个元素？但是，我将如何证明这一点？
<分区>
假设 f(n) ∈ O(log2(n))。我们可以说 2^f(n) ∈ O(n) 吗？ 我可能让自己感到困惑，但从数学上讲这不是真的吗？因为 2^log2(n) 是 n，而 n 就复杂度而言是 O(n) 的一个元素？但是，我将如何证明这一点？
最佳答案
不，这不是真的。你可以转换为
2^f(n) = n^O(1)
作为f(n) < c*log2(n) (对于大 n )仅意味着
2^f(n) < 2^(c*log2(n)) = (2^log2(n))^c = n^c
有一些未公开的常量 c .
关于algorithm - 如何证明这一点？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39578241/