Temps polynomial et temps exponentiel

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

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

Vérifiez ceci .

L'exponentiel est pire que le polynôme.

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

L'exponentiel est bien pire qu'un polynôme. Regardez comment les fonctions évoluent

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

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

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

Je ne l'ai pas calculé, mais C'EST SI GRAND.

Vous trouverez ci-dessous quelques fonctions Big-O courantes lors de l'analyse des algorithmes.

• O ( 1 ) - temps constant
• O ( log (n) ) - temps logarithmique
• O ( (log (n)) ^c ) - temps polylogarithmique
• O ( n ) - temps linéaire
• O ( n ² ) - temps quadratique
• O ( n ^c ) - temps polynomial
• O ( c ⁿ ) - temps exponentiel
• O ( n! ) - temps factoriel

(n = taille de l'entrée, c = une constante)

Voici le graphe modèle représentant la complexité Big-O de certaines fonctions

à votre santé :-)

crédits graphiques http://bigocheatsheet.com/

O (n ^ 2) est le temps polynomial. Le polynôme est f (n) = n ^ 2. D'autre part, O (2 ^ n) est le 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 beaucoup plus rapidement (à long terme) que toute fonction polynomiale, de sorte que la distinction est pertinente pour l'efficacité d'un algorithme, en particulier pour les grandes valeurs de n.

Temps polynomial.

Un polynôme est une somme de termes qui ressemblent à Constant * x^k Exponentiel signifie quelque chose commeConstant * 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 vite que celui des algorithmes polynomiaux.

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

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

Polynomial (Vous avez une fonction polynomiale si AUCUN EXPONENT dépend de certains paramètres de fonction):

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

temps polynomial O (n) ^ k signifie que le nombre d'opérations est proportionnel à la puissance k de la taille de l'entrée

temps exponentiel O (k) ^ n signifie que le nombre d'opérations est proportionnel à l'exposant de la taille de l'entrée

o (n sequre) est la complexité temporelle polynimale tandis que o (2 ^ n) est la complexité temporelle exponentielle si p = np dans le meilleur des cas, dans le pire des cas p = np pas égal parce que lorsque la taille d'entrée n augmente si longtemps ou que le taille d'entrée augmente donc plus il va vers le pire des cas et la gestion de la complexité augmente donc le taux de croissance et dépend de la taille n de l'entrée 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 sont également rencontrés en exponentiel en polynimal.