Qu'est-ce que O(log(n !)) et O(n !) et l'approximation de Stirling ?

Question

Qu'est-ce que O(log(n!)) y O(n!) ? Je crois que c'est O(n log(n)) y O(n^n) ? Pourquoi ?

Je pense que cela a un rapport avec l'approximation de Stirling, mais je ne comprends pas très bien l'explication.

Quelqu'un pourrait-il me corriger si je me trompe (à propos de O(log(n!) = O(n log(n)) ) ? Et si possible les mathématiques en termes plus simples ? Je ne pense pas que j'aurai besoin de prouver cela en réalité, je veux juste avoir une idée de comment cela fonctionne.

Answer 1

O(n!) n'est pas équivalent à O(n^n) . Elle est asymptotiquement inférieure à O(n^n) .

O(log(n!)) est égal à O(n log(n)) . Voici une façon de le prouver :

Notez qu'en utilisant la règle d'enregistrement log(mn) = log(m) + log(n) on peut le voir :

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

Preuve que O(log(n!)) ⊆ O(n log(n)) :

log(n!) = log(n) + log(n-1) + ... log(2) + log(1)

Ce qui est moins que :

log(n) + log(n) + log(n) + log(n) + ... + log(n) = n*log(n)

Alors O(log(n!)) est un sous-ensemble de O(n log(n))

Preuve que O(n log(n)) ⊆ O(log(n!)) :

log(n!) = log(n) + log(n-1) + ... log(2) + log(1)

Ce qui est plus grand que (la moitié gauche de cette expression avec tous les (n-x) remplacé par n/2 :

log(n/2) + log(n/2) + ... + log(n/2) = floor(n/2)*log(floor(n/2)) ∈ O(n log(n))

Alors O(n log(n)) est un sous-ensemble de O(log(n!)) .

Depuis O(n log(n)) ⊆ O(log(n!)) ⊆ O(n log(n)) ils sont équivalents à des classes de grands-Oh.

Answer 2

Par l'approximation de Stirling,

log(n!) = n log(n) - n + O(log(n))

Pour un grand n, le côté droit est dominé par le terme n log(n). Cela implique que O(log(n !)) = O(n log(n)).

Plus formellement, une définition de "Big O" est que f(x) = O(g(x)) si et seulement si

lim sup|f(x)/g(x)| < ∞ as x → ∞

En utilisant l'approximation de Stirling, il est facile de montrer que log(n !) ∈ O(n log(n)) en utilisant cette définition.

Un argument similaire s'applique à n ! En prenant l'exponentielle des deux côtés de l'approximation de Stirling, on trouve que, pour un grand n, n ! se comporte asymptotiquement comme n^(n+1) / exp(n). Puisque n / exp(n) → 0 comme n → ∞, on peut conclure que n ! ∈ O(n^n) mais que O(n !) n'est pas équivalent à O(n^n). Il existe des fonctions dans O(n^n) qui ne sont pas dans O(n !) (comme n^n lui-même).