Quelle fonction croît le plus rapidement, l'exponentielle ou la factorielle ?

Question

Quelle fonction croît plus rapidement, l'exponentielle (comme 2^n, n^n, e^n etc) ou la factorielle (n !)? Ps : Je viens de lire quelque part que n ! croît plus vite que 2^n.

Answer 1

N ! finit par croître plus vite qu'une exponentielle à base constante (2^n et e^n), mais n^n croît plus vite que n ! puisque la base croît lorsque n augmente.

Answer 2

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

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

Chaque trimestre après le premier dans n^n est plus grande, donc n^n croîtra plus vite.

Answer 3

n^n devient plus grande que n! -- pour une excellente explication, voir la réponse de @AlexQueue.

Pour les autres cas, lisez la suite :

Les fonctions factorielles deviennent asymptotiquement plus grandes que les fonctions exponentielles, mais il n'est pas évident de savoir quand la différence commence. Par exemple, pour n=5 y k=10 la factorielle 5!=120 est toujours plus petite que 10^5=10000 . Pour savoir quand les fonctions factorielles commencent à prendre de l'ampleur, nous devons procéder à une rapide analyse mathématique.

Nous utilisons la formule de Stirling et la manipulation de base des logarithmes :

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

Ainsi, une fois n atteint presque 3 fois la taille de k les fonctions factorielles commenceront à devenir plus importantes que les fonctions exponentielles. Dans la plupart des scénarios du monde réel, nous utiliserons de grandes valeurs de n et de petites valeurs de k Dans la pratique, on peut donc supposer que les fonctions factorielles sont strictement plus grandes que les fonctions exponentielles.

Answer 4

Je vais vous montrer une méthode plus graphique pour le prouver très facilement. Nous allons utiliser la division pour tracer le graphique d'une fonction, ce qui nous permettra de le démontrer très facilement.

Utilisons une fonction de division basique et ennuyeuse pour expliquer une propriété de la division.

Au fur et à mesure que l'expression augmente, l'évaluation de cette expression augmente également. Lorsque b diminue, l'évaluation de cette expression diminue également.

En utilisant cette idée, nous pouvons tracer un graphique basé sur ce que nous nous attendons à voir augmenter et diminuer, et faire une comparaison pour savoir ce qui augmente le plus vite.

Dans notre cas, nous voulons savoir si les fonctions exponentielles croissent plus vite que les factorielles, ou vice versa. Nous avons deux cas, une constante vers un exposant variable vs une factorielle variable, et une variable vers un exposant variable vs une factorielle variable.

Le graphique de ces outils avec Desmos (aucune affiliation, c'est juste un bel outil), nous montre ceci :

Graphique d'une constante à exposant variable, vs factorielle variable

Bien qu'il semble au départ que l'expression exponentielle augmente plus rapidement, elle atteint un point où elle n'augmente plus aussi vite, mais où l'expression factorielle augmente plus rapidement.

Graphique d'une variable à exposant variable, vs factorielle variable

Bien qu'elle semble initialement être plus lente, elle commence à augmenter rapidement au-delà de ce point, nous pouvons donc conclure que l'exponentielle doit augmenter plus rapidement que la factorielle.