pmu*_*ima 4 algorithm asymptotic-complexity
我很确定前一个函数增长得更快.但是当我把它绘制在Wolfram alpha上时,后者似乎占主导地位.
通常,如果我想比较f(n)和g(n),可以使用log(f(n))和log(g(n))的分析来分析原始函数吗？
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.