其中增长得更快2 ^（2^n）或n ^（2n）

Question

我很确定前一个函数的增长速度更快。但是当我将它绘制在Wolfram alpha上时，后者似乎占主导地位。一般来说，如果我想比较f（n）和g（n），可以使用log（f（n））和log（g（n））的分析来分析原始函数吗？

Answer 1

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做什么。 2^2^n主导n^(2*n)甚至对于单个数字n：2^(2^9)约为1.34 x 10^154，但9^(2*9)仅为1.5 x 10^17。