文章/答案/技术大牛

发布

社区首页 >问答首页 >哪个增长快2^(2^n)或n^(2n)

问哪个增长快2^(2^n)或n^(2n)
EN

Stack Overflow用户

提问于 2017-01-23 08:38:19

回答 1查看 898关注 0票数 4

我非常确定前一个函数增长得更快。但当我把它绘制在Wolfram alpha上时，后者似乎占据了主导地位。

一般来说，如果我想比较f(n)和g(n)，可以使用log(f(n))和log(g(n))的分析来分析原始函数吗？

algorithm

asymptotic-complexity

回答 1

Stack Overflow用户

回答已采纳

发布于 2017-01-23 08:46:51

log(x)是一个递增函数，因此f(x) <= g(x)当且仅当log(f(x)) <= log(g(x))。

在这种情况下，

log(2^2^n) = 2^n*log(2)

这是指数级增长。

但

log(n^(2*n)) = 2*n*(log(n)) = O(nlog(n))

这是次指数的。

因此，您认为2^2^n逐渐主导n^(2*n)的观点是正确的。

我不知道你对Wolfram Alpha做了什么。即使对于个位数n，也可以看到2^2^n支配n^(2*n)的事实：2^(2^9)近似为1.34 x 10^154，而9^(2*9)仅为1.5 x 10^17。

票数 7

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/41797742

复制

相似问题

问哪个增长快2^(2^n)或n^(2n)
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问哪个增长快2^(2^n)或n^(2n)EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问哪个增长快2^(2^n)或n^(2n)
EN