哪个函数增长得更快，指数函数还是阶乘函数？

小开

最佳答案

n! eventually grows faster than an exponential with a constant base (2^n and e^n), but n^n grows faster than n! since the base grows as n increases.

小开

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

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

Every term after the first one in n^n is larger, so n^n will grow faster.

小开

n^n grows larger than n! -- for an excellent explanation, see the answer by @AlexQueue.

For the other cases, read on:

Factorial functions do asymptotically grow larger than exponential functions, but it isn't immediately clear when the difference begins. For example, for n=5 and k=10, the factorial 5!=120 is still smaller than 10^5=10000. To find when factorial functions begin to grow larger, we have to do some quick mathematical analysis.

We use Stirling's formula and basic logarithm manipulation:

log_k(n!) ~ n*log_k(n) - n*log_k(e)


k^n = n!
log_k(k^n) = log_k(n!)
n*log_k(k) = log_k(n!)
n = log_k(n!)


n ~ n*log_k(n) - n*log_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/(e*k)) ~ 0


n/(e*k) ~ 1
n ~ e*k

Thus, once n reaches almost 3 times the size of k, factorial functions will begin to grow larger than exponential functions. For most real-world scenarios, we will be using large values of n and small values of k, so in practice, we can assume that factorial functions are strictly larger than exponential functions.

小开

I want to show you a more graphical method to very easily prove this. We're going to use division to graph a function, and it will show us this very easily.

Let's use a basic and boring division function to explain a property of division.

As a increases, the evaluation of that expression also increases. As a decreases, the evaluation of that expression also decreases.

Using this idea, we can plot a graph based on what we expect to increase, and expect to decrease, and make a comparision as to which increases faster.

In our case, we want to know whether exponential functions will grow faster than factorials, or vice versa. We have two cases, a constant to a variable exponent vs. a variable factorial, and a variable to a variable exponent vs a variable factorial.

Graphing these tools with Desmos (no affiliation, it's just a nice tool), shows us this:

Graph of a constant to variable exponent, vs variable factorial

Although it initially seems that the exponential expression increases faster, it hits a point where it no longer increases as fast, and instead, the factorial expression is increasing faster.

Graph of a variable to variable exponent, vs variable factorial

Although it initially seems to be slower, it begins to rise rapidly past that point, therefore we can conclude that the exponential must be increasing faster than the factorial.