f(n) = n^5 + 2^log(n) 的大 O 应该是多少？

Question

我遇到了一个问题，我必须 select 函数 f(n) = n^5 + 2^log(n)[=16 的正确大 O =]... 我尝试输入较大的值，发现 n^5 与 2^log(n) 相比增长显着......但后来有人告诉我指数函数与其他函数相比增长显着......我再次感到困惑。 ..老实说，我认为 2^log(n) 不是指数函数...但是由于我的对数概念薄弱，我无法证明...

I just want someone to tell me that yes n^5 is larger than 2^log(n) so that I can prove that 2^log(n) is not an exponential function...

提前致谢。 :)

Answer 1

2^log(n) = (2/e)^log(n) * e^log(n) = a^log(n) * n 其中a = 2/e < 1（假设log是自然对数）。

因此 f(n) = n^5 + 2^log(n) < n^5 + n 因此 f(n) = O(n^5)。

---

[ EDIT ] 在任意基数 b 的对数的一般情况下，使用 2 = b^log_b(2) 得出：

    2^log_b(n) = (b^log_b(2))^(log_b(n))
               = b^(log_b(2)*log_b(n))
               = (b^log_b(n))^log_b(2)
               = n^log_b(2)
               = n^(1/log_2(b))

因此f(n) = n^5 + log_b(n) = O( n^5 + n^(1/log_2(b)) ) = O( n^max(5, 1/log_2(b)) ).

特别是 f(n) = O(n^5) 对应 log_2(b) > 1/5 ⇔ b > 2^(1/5)，它涵盖了 2、e、10 的常见 log 碱基。

Answer 2

O(2^logn)=O(n) - 这直接来自对数的定义。

更正式地说：

f(n)=2^logn

log₂f(n)=log₂(2^logn)=lognlog ₂2=log₂n ==>f(n)=n

==> O(2^logn)=O(n)

==> O(n⁵ + 2^logn)=O(n⁵ + n)=O(n⁵)