Temps polynomial et temps exponentiel

Question

Quelqu'un pourrait-il expliquer la différence entre les algorithmes à temps polynomial, à temps non polynomial et à temps exponentiel ?

Par exemple, si un algorithme prend un temps O(n^2), dans quelle catégorie se trouve-t-il ?

Answer 1

Vérifiez este dehors.

L'exponentiel est pire que le polynomial.

O(n^2) tombe dans la catégorie quadratique, qui est un type de polynôme (le cas particulier de l'exposant étant égal à 2) et mieux que l'exponentiel.

L'exponentiel est beaucoup pire que polynomial. Regardez comment les fonctions croissent

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

k^n  = k^10  |   k^100   |    k^1000

k^1000 est exceptionnellement énorme à moins que k soit plus petit que quelque chose comme 1,1. Par exemple, chaque particule de l'univers devrait effectuer 100 milliards de milliards de milliards d'opérations par seconde pendant des trillions de milliards de milliards d'années pour y parvenir.

Je ne l'ai pas calculé, mais il est si grand.

Answer 2

O(n^2) est un temps polynomial. Le polynôme est f(n) = n^2. D'autre part, O(2^n) est un temps exponentiel, où la fonction exponentielle impliquée est f(n) = 2^n. La différence est de savoir si la fonction de n place n dans la base d'une exponentiation, ou dans l'exposant lui-même.

Toute fonction de croissance exponentielle croîtra significativement plus vite (à long terme) que toute fonction polynomiale. La distinction est donc pertinente pour l'efficacité d'un algorithme, en particulier pour les grandes valeurs de n.

Answer 3

Temps polynomial.

Un polynôme est une somme de termes qui ressemblent à Constant * x^k Exponentiel signifie quelque chose comme Constant * k^x

(dans les deux cas, k est une constante et x est une variable).

Le temps d'exécution des algorithmes exponentiels croît beaucoup plus rapidement que celui des algorithmes polynomiaux.

Answer 4

Exponentiel (Vous avez une fonction exponentielle si MINIMAL UNE EXPONENCE dépend d'un paramètre) :

• Par exemple, f(x) = constante ^ x

Polynôme (Vous avez une fonction polynomiale si NO EXPONENT dépend de certains paramètres de la fonction) :

• Par exemple : f(x) = x ^ constant

Answer 5

O(n sequre) est une complexité en temps polynimale alors que o(2^n) est une complexité en temps exponentielle si p=np dans le meilleur des cas, dans le pire des cas p=np n'est pas égal parce que lorsque la taille de l'entrée n augmente tellement ou que le dimensionnement de l'entrée augmente tellement que cela va vers le pire des cas et la manipulation donc le taux de croissance de la complexité augmente et dépend de la taille de l'entrée n lorsque l'entrée est petite elle est polynimale lorsque la taille de l'entrée est grande et grande donc p=np n'est pas égal cela signifie que le taux de croissance dépend de la taille de l'entrée "N". optimisation, sat, clique, et ensemble indépendant se rencontrent aussi en exponentiel à polynimal.