其中增長得更快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。