Polynomzeit und Exponentialzeit

Könnte jemand den Unterschied zwischen Algorithmen für Polynomzeit, Nicht-Polynomzeit und Exponentialzeit erklären?

Wenn ein Algorithmus beispielsweise O (n ^ 2) Zeit benötigt, in welcher Kategorie befindet er sich dann?

Überprüfen Sie dies heraus.

Exponentiell ist schlimmer als Polynom.

O (n ^ 2) fällt in die quadratische Kategorie, die eine Art Polynom ist (der Sonderfall, dass der Exponent gleich 2 ist) und besser als exponentiell ist.

Exponentiell ist viel schlimmer als Polynom. Schauen Sie sich an, wie die Funktionen wachsen

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

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

k ^ 1000 ist außergewöhnlich groß, es sei denn, k ist kleiner als so etwas wie 1.1. So etwas wie jedes Teilchen im Universum müsste 100 Milliarden Milliarden Operationen pro Sekunde ausführen, damit Billionen von Milliarden von Milliarden von Jahren dies erreichen.

Ich habe es nicht berechnet, aber es ist so groß.

Im Folgenden finden Sie einige allgemeine Big-O-Funktionen für die Analyse von Algorithmen.

• O ( 1 ) - konstante Zeit
• O ( log (n) ) - logarithmische Zeit
• O ( (log (n)) ^c ) - polylogarithmische Zeit
• O ( n ) - lineare Zeit
• O ( n ² ) - quadratische Zeit
• O ( n ^c ) - Polynomzeit
• O ( c ⁿ ) - Exponentialzeit
• O ( n! ) - Fakultätszeit

(n = Größe der Eingabe, c = eine Konstante)

Hier ist das Modelldiagramm, das die Big-O-Komplexität einiger Funktionen darstellt

Prost :-)

Grafik Credits http://bigocheatsheet.com/

O (n ^ 2) ist die Polynomzeit. Das Polynom ist f (n) = n ^ 2. Andererseits ist O (2 ^ n) die Exponentialzeit, wobei die implizierte Exponentialfunktion f (n) = 2 ^ n ist. Der Unterschied besteht darin, ob die Funktion von n n in die Basis einer Potenzierung oder in den Exponenten selbst setzt.

Jede exponentielle Wachstumsfunktion wächst signifikant schneller (langfristig) als jede Polynomfunktion, daher ist die Unterscheidung für die Effizienz eines Algorithmus relevant, insbesondere für große Werte von n.

Polynomzeit.

Ein Polynom ist eine Summe von Begriffen, die so aussehen, als würde Constant * x^k Exponential so etwas bedeutenConstant * k^x

(In beiden Fällen ist k eine Konstante und x eine Variable).

Die Ausführungszeit von Exponentialalgorithmen wächst viel schneller als die von Polynomen.

Exponential (Sie haben eine Exponentialfunktion, wenn MINIMAL ONE EXPONENT von einem Parameter abhängig ist):

• ZB f (x) = Konstante ^ x

Polynom (Sie haben eine Polynomfunktion, wenn NO EXPONENT von einigen Funktionsparametern abhängig ist):

• ZB f (x) = x ^ Konstante

Polynomzeit O (n) ^ k bedeutet Anzahl der Operationen ist proportional zur Leistung k der Eingangsgröße

Exponentialzeit O (k) ^ n bedeutet Anzahl der Operationen ist proportional zum Exponenten der Eingangsgröße

o (n sequre) ist die polynimale Zeitkomplexität, während o (2 ^ n) die exponentielle Zeitkomplexität ist, wenn p = np im besten Fall ist, im schlimmsten Fall p = np nicht gleich, weil die Eingangsgröße n so lang wird oder die Eingangsgröße so zunimmt länger ist es der schlimmste Fall und die Handhabung, so dass die Wachstumsrate der Komplexität zunimmt und von der n-Größe der Eingabe abhängt, wenn die Eingabe klein ist. Es ist polynimal, wenn die Eingabegröße groß und groß ist, so dass p = np nicht gleich ist. Dies bedeutet, dass die Wachstumsrate von der Größe der Eingabe abhängt. "N. ". Optimierung, Sat, Clique und Independ Set trafen sich ebenfalls exponentiell bis polynimal.