algorithm - 比较两个函数的增长率。 (棘手)

Question

我需要比较以下函数的增长率:

f(n)=2^n 和 g(n)=n^log(n)(当 n 接近正无穷大时)。

这可能吗？

Answer 1

令 n = 2^k。我们有:

2^n = 2^(2^k)
n^log(n) = (2^k)^log(2^k) = (2^k)^(k log 2)
         = 2^(k^2 log 2)

现在比较 2^k 和 k^2 log 2。这是一个基本比较:对于所有足够大的 k，2^k 都更大。