2^(2^n) 或 n^(2n) 哪个增长更快
Which grows faster 2^(2^n) or n^(2n)
我很确定前一个函数增长得更快。但是当我在 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))
也就是 sub-exponential.
因此，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.
我很确定前一个函数增长得更快。但是当我在 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))
也就是 sub-exponential.
因此，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.