比较增长率：n·lg(n) 和 0.02·n^(1.01)。哪一个增长更快？

Question

比较n·lg(n)和0.02·n^(1.01)，哪个增长更快?

我可以把n^(1.01)写成n·n^(0.01)

这样做，问题就变成了:如何比较lg(n)和n^0.01。

但是我不知道lg(n)和n^0.01哪个长得更快。

我怎样才能解决这个问题?

Answer 1

对数的增长速度比任何正幂都慢。假设lg是十进制对数，0.02 n^(1.01)将在n ~= 4.04192e+433处超过n lg(n)(参见Wolphram Alpha查询)。如果是关于计算复杂度的实际问题，对于合理的n值，0.02 n^(1.01)算法可能会比n lg(n)算法更快。

Answer 2

要查看哪个函数增长得更快，可以计算极限

lim f(n)/g(n)

如果是0，则g(n)的增长速度快于f(n)，如果是∞，则f(n)的增长速度快于g(n)，如果是任何其他数字，则它们的增长速度相同。

来计算这种极限的洛必达法则是有帮助的。它说

lim f(n)/g(n) = lim f'(n)/g'(n)

其中f'(n)为f(n)的微分。

在你的例子中，你必须计算

<>之前lim n <一口> 0.01> 0.99> 0.99 = lim n <一口> 0.01 =∞之前

所以n0.01比ln n生长得快。