哪个函数增长得更快，指数还是因子？

Question

哪个函数增长得更快，指数（如2 ^ n，n ^ n，e ^ n等）或阶乘（n！）？ Ps：我刚读到某个地方，n！增长快于2 ^ n。

Answer 1

N！最终比具有常数基数（2 ^ n和e ^ n）的指数增长更快，但是n ^ n比n增长更快！因为基数随着n的增加而增长。

Answer 2

n! = n * (n-1) * (n-2) * ...

n^n = n * n * n * ...

在n^n中第一个术语之后的每个术语都更大，因此n ^ n将增长得更快。

Answer 3

因子时间算法渐近运行比指数时间算法慢，但是差异开始时并不是立即清楚。例如，对于n=5和k=10，5!=120仍然比10^5=10000更快。为了找到指数时间算法开始表现更好的时候，我们必须做一些快速的数学分析。

我们可以使用斯特林的公式：

log_k^(n!) ~ nlog_k^n - nlog_k^e

k^n = n!
log_k^{k^n} = log_k^{n!}
n = log_k^{n!}

n ~ nlog_k^n - nlog_k^e
1 ~ log_k^n - log_k^e
log_k^n - log_k^e - 1 ~ 0
log_k^n - log_k^e - log_k^k ~ 0
log_k^{n/(ek)} ~ 0

n/(ek) ~ 1
n ~ ek

因此，一旦n达到k大小的3倍，因子时间算法将开始比指数时间算法慢。对于大多数现实场景，我们将使用n的较大值和k的较小值，因此在实践中，我们可以假设阶乘时间算法严格地比指数时间算法差。