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

Question

我遇到了一个问题，我必须为函数f(n) = n^5 + 2^log(n)选择正确的大 O... 我尝试输入较大的值，发现与 2^log(n) 相比，n^5 显着增长...但后来有人告诉我，与其他函数相比，指数函数显着增长......我又糊涂了...老实说，我认为 2^log(n) 不是一个指数函数......但是由于我的对数概念很弱，我无法证明这一点......

我

只是想有人告诉我是的 n^5 大于 2^log(n)，这样我就可以证明 2^log(n) 不是一个指数函数......

提前谢谢。:)

Answer 1

2^log(n) = (2/e)^log(n) * e^log(n) = a^log(n) * na = 2/e < 1的位置(假设log是自然对数)。

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

---

[编辑] 在任意底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)) ).

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

Answer 2

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

更正式地说：

f(n)=2^logn

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

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

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