O (n Log n) est-il en temps polynomial?

Est O(n Log n) en temps polynomial? Si oui, pourriez-vous expliquer pourquoi?

Je suis intéressé par une démonstration mathématique, mais je serais reconnaissant pour toute forte intuition.

Merci!

source d'informationauteur Yahiko Kikikoto

  1. 10

    Oui, O(nlogn) est polynomial en temps.

    De http://mathworld.wolfram.com/PolynomialTime.html:

    Un algorithme est dit résoluble en temps polynomial si le nombre
    des étapes nécessaires pour compléter l'algorithme pour une entrée donnée est
    O(n^m) pour un certain entier positif m, où n est la complexité de
    l'entrée.

    De http://en.wikipedia.org/wiki/Big_O_notation:

    f est O(g) ssi

    O (n Log n) est-il en temps polynomial?

    Je vais maintenant prouver que n log n est O(n^m) pour un certain m, ce qui signifie que n log n est polynomial en temps.

    En effet, de prendre m=2. (ce qui signifie que je vais prouver que n log n est O(n^2))

    La preuve, prenons k=2. (Ce pourrait être plus faible, mais il n'est pas obligatoire.)
    Il existe une n_0 tels que pour tous les plus grands n la suite détient.

    n_0 * f(n) <= g(n) * k

    Prendre n_0 = 1 (c'est suffisant)
    Il est maintenant facile de voir que

    n log n <= 2n*n

    log n <= 2n

    n > 0 (hypothèse)

    Cliquez sur ici si vous n'êtes pas sûr à ce sujet.

    Cette preuve pourrait être beaucoup plus agréable en latex de mathématiques de mode, mais je ne pense pas que stackoverflow prend en charge que.

  2. 3

    Il est, car il est haut-bornée par un polynôme (n).
    Vous pourriez jeter un oeil à des graphiques et à partir de là, mais je ne peux pas formuler une preuve mathématique autre que ça 😛

    EDIT: a Partir de la page de wikipedia, "Un algorithme est polynomial en temps si son temps d'exécution est supérieur délimitée par une expression polynomiale en la taille de l'entrée pour l'algorithme".

  3. 2

    Il est au moins pas pire que temps polynomial. Et toujours pas mieux: n < n log n < n*n.

  4. -1

    Oui. Quelle est la limite de nlogn que n tend vers l'infini? Intuitivement, pour n grand, n >> logn et vous pouvez considérer que le produit dominé par n et donc nlogn ~ n, qui est clairement temps polynomial. Une preuve de plus de rigueur est en utilisant le théorème du Sandwich qui a Inspiré:

    n^1 < nlogn < n^2.

    Donc nlogn est délimitée ci-dessus (et ci-dessous) par une séquence qui est polynomial en temps.