prouver que n! = O(n^n)

Mise à jour: Désolé j'ai oublié de mettre n^n à l'intérieur de l'O()

Ma tentative était de résoudre cette relation de récurrence:

T(n) = nT(n-1) +1
T(0) = 1;

À l'aide de la méthode itérative j'ai eu le n^n, mais Im pas sûr si c'est la façon de le prouver.

Êtes-vous essayer de prouver que O(n!) et O(n^n) sont-elles équivalentes? Ce n'est pas le cas.
Quoi? (n!) != (n^n). Non seulement cela, mais votre première ligne devrait lire T(n) = n T(n-1) -- c'est à dire, la chute de la +1.
J'espère qu'il n'essaie pas de prouver que O(n!) et O(n^n) sont équivalents, car ils ne sont pas. (n^n est plus grand par un facteur qui peut être grossièrement approchée comme e^n.)
Ils ne sont pas équivalents, ni O(n!) et O(n^n). n! est O(n^n) (presque trivialement, par la définition), mais pas l'inverse. Est-ce que vous voulez montrer?
T(n) = nT(n-1) +1 ne serait pas n!. n! serait T(n) = nT(n-1)

OriginalL'auteur Wilbert Barrera | 2011-02-15

  1. 19

    Je suppose que vous voulez prouver que la fonction n! est un élément de l'ensemble O(n^n). Cela peut être prouvé assez facilement:

    Définition: Une fonction f(n) est élément de l'ensemble O(g(n)) si il existe un c>0 telle qu'il existe un m tel que pour tout k>m nous avons que f(k)<=c*g(k).

    Donc, il nous faut comparer n! contre n^n. Nous allons écrire l'une sous l'autre:

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

    Comme vous pouvez le voir, la première ligne (n!) et la deuxième ligne (n^n) ont tous deux exactement n éléments du côté droit. Si l'on compare ces éléments, nous voyons que chaque élément est au plus aussi grand qu'il l'élément correspondant dans la deuxième ligne. Ainsi n! <= n^n (au moins pour n>5).

    Donc, nous pouvons regarder la définition - dire, qu'il existe c=1 qu'il existe, m=5 tel que pour tout k>5 nous avons que k! < k^k, ce qui prouve que n! est en effet un élément de O(n^n).

    Pour formaliser cela, vous pouvez facilement le transformer en induction.

    OriginalL'auteur phimuemue

  2. 8

    Remarque: ce qui suit est une réponse à la Question de départ qui était: "Prouver que n! = n^n"

    Je peux prouver que c'est pas vrai assez facilement: prendre n = 5.

    n! = 120
n^n = 3125
    Trop littérale, je suppose. Je pense que l'échec est la voie de l'OP libellé de la question, pas ma réponse.
    AUCUNE idée de pourquoi downvote. +1.
    Avoir un upvote. GIGO.
    Si vous regardez l'historique des modifications de la question, l'original de la présente l'hypothèse que n! = n^n. Le Grand-Oh notation a été ajouté après ma réponse. Ma réponse est tout à fait correcte pour la question qui a été présenté quand je l'ai écrit. Vous avez été sur ce site pour deux ans. Est-ce la meilleure contribution que vous pouvez faire, à un troll et des commentaires sur les deux ans des réponses? Aller répondre à une question et d'essayer d'aider quelqu'un.
    troll" peut être offensant pour la personne qui accomplit tout en les commentant.

    OriginalL'auteur duffymo

  3. 2

    Il n'est pas vrai que n! = n^n, et, par conséquent, vous ne serez pas en mesure de prouver que. En outre, la solution à votre relation de récurrence est ni n! ou n^n. (Il satisfait à T(1) = 1*1+1 = 2, qui n'est ni 1! ni 1^1.)

    Exactement ce que vous essayez de faire, et pourquoi?

    il va à faire à propos de l'estimation de la complexité de l'algorithme. Il n'est pas n! = n^n que le sens habituel.

    OriginalL'auteur Gareth McCaughan

  4. 0

    n! != n^n. Cependant, la T(n) séquence définie ci-dessus n'est pas n!. Mais il égal n^n? Pour n=1, T(1) = 1*T(0) + 1 = 1*1 + 1 = 2 mais n^n = 1^1 = 1. Cependant, en supposant que vous signifiait aussi T(1) = 1, alors qu'ils sont égaux pour n=1. Allant plus loin encore, pour n=2, puis T(2) = 2*T(1) + 1 = 2*1 + 1 = 3 != 2^2. Donc, je suis franchement pas sûr de ce que vous êtes en train de demander.

    Évidemment, cette notation est d'abuser de l'égalité symbole, car elle viole l'axiome de l'égalité: "les choses égales à une même chose sont égales entre elles". Plus formellement correctes, certaines personnes (surtout les mathématiciens, par opposition à des informaticiens) préfèrent définir O(g(x)) comme un ensemble d'une fonction de valeurs, dont la valeur est l'ensemble des fonctions qui ne font pas croître plus vite alors g(x), et d'utiliser l'appartenance de notation pour indiquer qu'une fonction est un membre de l'ensemble ainsi défini. Les deux formes sont dans l'usage commun, mais la bâclé l'égalité de notation est plus fréquente à l'heure actuelle

    OriginalL'auteur user470379

  5. 0

    pour n==2, n! = 2 != 4 = n^n.

    pour n!=2, (n-1) divise n! mais n-1 ne pas diviser n^n (n^n mod n-1 == 1)

    Le réel de l'approximation de stirling est n! ~ sqrt(2 Pi n) (n/e)^n

    Quelle est votre formation mathématique? Voulez-vous un complexe analytique preuve ou quelque chose de plus combinatoire dans la nature?

    merci de me donner l'occasion de se remémorer collège 🙂
    c'est une merde à la preuve. Il y a beaucoup plus générale de l'approximation de stirling, qui implique que la fonction gamma [qui vous le prouver par le calcul des résidus]
    Je suis un math guy au cœur, et sa fait des années que je n'ai pas pensé difficile en mathématiques. Et oui, de vrais cours de mathématiques sont pinailleurs 🙂
    Oui, les cours de mathématiques sont pinailleurs 🙂 btw, tu sais on peut défaire les downvotes? Une fois que vous modifier votre réponse à inclure ce cas, je vais enlever le downvote. btw, tu crois vraiment que quelqu'un qui poste une telle question sera de savoir l'analyse complexe? Aussi, Euler McLaurin la Sommation de la formule est un outil très utile. Dommage que vous pensez que c'est merdique. De toute façon...
    Je ne pense pas que ses une merde outil en général; ses une merde outil dans ce cas, car, autant que j'ai pu suivre la preuve dans ma tête, vous ne pourriez pas obtenir ce supplément de sqrt(n) terme

    OriginalL'auteur Foo Bah