Comment puis-je prouver que n! n'est pas dans O (n^p) pour un nombre naturel constant p? Et est (n k) (n choisir k) dans O (n^p), pour tout k?Prouvez que n! n'est pas dans O (n^p) pour un nombre naturel constant p
Vous pouvez prouver que n! n'est pas dans O (n^p) pour tout nombre naturel constant p, en montrant que vous pouvez toujours choisir n (pour une constante p fixe), de sorte que n! > n^p.
(pour avoir une idée, prendre quelques faibles valeurs de p et n complot! Contre n^p)
Le raisonnement pour la deuxième partie suit les mêmes lignes. Lié (n choisissez k) puis utilisez la première partie.
Astuce: Casablanca comme noté, vous pouvez utiliser Stirling's approximation
Pour être précis, * pour tous * n> n0, où n0 est un nombre entier positif. Vous ne pouvez pas choisir une seule valeur n. Contre-exemple: p = 10, n = 2. 2^10> 2 !. –
Je suis désolé, je devrais réviser ce commentaire. Pour * réfuter * n! = O (n^p): donné p, alors pour * any * n0> 0, il existe une (unique) valeur n> n0 telle que n! > n^p. –
Stirling's approximation dit que
log (n!) = n log n - n + O(log n) = O(n log n)
Mais
log (n^p) = p log n = O(log n)
pour p constante. Clairement n! croît plus vite que n^p et par conséquent ce n'est pas O(n^p).
Vous pouvez également noter sans utiliser l'approximation de stirlings que log (n!) = Log (n) + log (n-1) + ... + log (2) + log (1). log (1) = 0, donc tous les autres termes doivent être _at least_log (2) ou plus. Cela donne log (n!)> N * log (2), ce qui signifie bien sûr que c'est O (n). Comme vous l'avez noté, c'est en fait O (n * log n), mais O (log n) croît aussi beaucoup plus vite que O (log n). –
+1. J'essayais de ne pas faire les devoirs pour eux;). mais j'aurais probablement dû faire allusion à l'approximation factorielle de Stirling. –
Edit (3/2011) - (! N) méthode plus simple en utilisant uniquement le calcul simple,
Une façon de montrer O ne correspond pas à O (n^p) est de comparer le journal de n! avec le journal de n^p.
ln (n!) = Somme (ln (i)) {i: 1 à n}
ln (n^p) = p * ln (n)
Cela ne semble pas pour aider puisque nous ne savons pas quelle serait la somme des logs. L'astuce consiste à calculer une borne inférieure en utilisant l'intégrale de ln (i) di de 1 à n
Ceci peut être vu dans l'image ci-dessous que le ln (x) en noir est inférieur à la fonction de pas de somme dans bleu.
Étant donné que l'intégrale indéfinie de ln (i) di est i * ln (i) - i + C, nous pouvons intégrer de 1 à n pour obtenir:
n * ln (n) - n + 1 comme borne inférieure.
Et parce que p peut être choisi qui est plus grand que possible n:
O (p ln (n)) < O (n ln (n)), O (n^p) < O (n!)
note: l'intégration de ln (n) pour obtenir une approximation de ln (n!) Est la base de l'approximation de Stirling. C'est une approximation plus grossière et si vous continuez en prenant l'anti-log: n! > = e * (n/e)^n, alors que Stirling a sqrt (2 * pi * n) au lieu de e.
Intégration de 1 à n + 1 vous donnerait une limite supérieure (la fonction étape de somme correspondrait à l'intérieur du graphique de ln (n))
@Mitch: Si vous avez fait qu'une réponse, je voudrais Upvote il. –
@Tony: ["la balise homework, comme les autres balises" meta ", est maintenant déconseillée."] (Http://meta.stackexchange.com/q/10812) –