我需要比较以下函数的增长率:
f(n)=2^n 和 g(n)=n^log(n) (当 n 趋近正无穷时)。
这是否可能呢?
让 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
更大。对两个函数同时进行以2为底的对数运算,我们得到 log(f(n)) = n
,其中 log(g(n)) = (log(n))^2
。
现在,(log(n))^2 = o(n)
,而且log
是一个单调递增的函数,因此我们有
g(n) = o(f(n))
,也就是说,f(n)
在n
很大时增长得更快。
以下是另一种更严谨的证明方法:
令L = lim{n->inf} g(n) / f(n) = lim{n->inf} n^(log(n))/2^n
。
因此,log(L) = lim{n->inf} log^2(n) - n
` = lim{n->inf} n*(log^2(n)/n) - 1)`
` = lim{n->inf} (n) * lim{n->inf} (log^2(n)/n) - 1)`
` = lim{n->inf} (n) * (0-1)`
` = lim{n->inf} (-n) = -inf`
=> L = 2 ^ (-inf) = 0
根据 o(n)
的另一种定义(小写字母 o,参见此处:https://en.wikipedia.org/wiki/Big_O_notation),
L = lim{n->inf} g(n) / f(n) = 0
=> g(n) = o(f(n))
。
以下是原始数据和对数坐标下比较 f(n)
和 g(n)
增长的图表:
(a^x)^y = a^(x*y)
。这里有一个例子:http://www.icoachmath.com/math_dictionary/power_properties.html。 - IVlad