f(n) = n^5 + 2^log(n)的大O应该是什么？
f(n) = n^5 + 2^log(n)的大O应该是什么？
提问于 2020-11-22 07:48:40
我遇到了一个问题，我必须为函数f(n) = n^5 +2^log(N)选择正确的Big .我试着放大的值，发现与2^log(N)相比，n^5有显著的增长。但后来有人告诉我指数函数比其他函数有很大的增长…我又糊涂了..。老实说，我认为2^log(n)不是指数函数.但由于我的弱对数概念，我无法证明.
，我只希望有人告诉我，是的n^5大于2^log(n)，这样我就可以证明2^log(n)不是指数函数.
提前谢谢。:)
回答 1
Stack Overflow用户
发布于 2020-11-22 07:55:45
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)。
在任意基数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) for log_2(b) > 1/5 ⇔ b > 2^(1/5)，它涵盖了2、e、10的公共log基。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64951758
复制相关文章
相似问题
腾讯云开发者
