Ich habe eine Frage über den Unterschied zwischen polynomischen Zeitalgorithmen, nicht polynomischen Zeitalgorithmen und exponentiellen Zeitalgorithmen zum Beispiel, wenn ein Algorithmus O (n^2) Zeit braucht, in welcher Kategorie wird er dann sein?Polynomische Zeit und exponentielle Zeit
check this out
http://en.wikipedia.org/wiki/Big_oh#Orders_of_common_functions
exponentiell ist schlimmer als Polynom.
O (n^2) fällt in die quadratische Kategorie, die eine Art Polynom ist (der Sonderfall des Exponenten ist gleich 2) und besser als exponentiell.
Exponential ist viel schlechter als Polynom. Schauen Sie, wie die Funktionen wachsen
n = 10 | 100 | 1000
n^2 = 100 | 10000 | 1000000
k^n = k^10 | k^100 | k^1000
k^1000 außergewöhnlich ist riesig, es sei denn k kleiner ist als so etwas wie 1.1 ist. Zum Beispiel müsste so etwas wie jedes Teilchen im Universum 100 Milliarden Milliarden Milliarden Operationen pro Sekunde für Billionen Milliarden von Jahren machen, um das zu erreichen.
Ich habe es nicht berechnet, aber ITS THAT BIG.
Polynomzeit.
Ein Polynom eine lineare Kombination von Termen ist, die auf dem gegenüberliegenden wie Constant * x^k aussehen, bedeutet exponentiell etwas wie k^x, wobei in beiden Fällen k eine Konstante ist und x ist eine Variable.
Die Ausführungszeit von Exponentialalgorithmen wächst viel schneller als die von Polynomen.
O (n^2) ist die Polynomzeit. Das Polynom ist f (n) = n^2. Auf der anderen Seite ist O (2^n) die Exponentialzeit, wobei die implizite Exponentialfunktion f (n) = 2^n ist. Der Unterschied besteht darin, ob die Funktion von n in die Basis einer Exponentiation oder in den Exponenten selbst gestellt wird.
Jede exponentielle Wachstumsfunktion wird signifikant schneller (längerfristig) wachsen als jede Polynomfunktion, so dass die Unterscheidung für die Effizienz eines Algorithmus relevant ist, insbesondere für große Werte von n.
Exponential (Sie haben eine Exponentialfunktion, wenn MINIMAL ONE EXPONENT auf einem Parameter abhängig ist):
Polynomial (Sie haben eine Polynomfunktion wenn NO EXPONENT auf einige Funktionsparameter abhängig ist):
Ich mag es nicht, wenn nichts von meiner ursprünglichen Antwort übrig ist, nachdem es von einem Benutzer bearbeitet wurde. Ist das eine Art "Fischfang"? –
Ich muss zustimmen. Die Änderungen sind lächerlich. –
o (n sequre) ist polynimal Zeitkomplexität während o (2^n) ist exponentielle Zeitkomplexität wenn p = np wenn bester Fall, im schlimmsten Fall p = np nicht gleich, wenn die Eingabegröße n so lange wächst oder der Eingabe-Sizer zunimmt, so dass es in den schlechtesten Fall geht und die Komplexität der Wachstumsrate so zunimmt und von der n Größe der Eingabe abhängt, wenn die Eingabe klein ist, ist sie polynimal, wenn die Eingabegröße groß und groß ist = np nicht gleich bedeutet, dass die Wachstumsrate von der Größe der Eingabe "N" abhängt. Optimierung, Sat, Clique und unabhängige Menge auch in exponentiell zu polynimal getroffen.
Polynom Zeit O (n)^k bedeutet die Anzahl der Operationen zur Leistungs k von der Größe des Eingangs proportional ist
exponentielle Zeit O (k)^n bedeutet die Anzahl der Operationen zu dem Exponenten der Größe proportional des Eingangs
Im Folgenden sind einige gebräuchliche Big-O-Funktionen bei der Analyse von Algorithmen aufgeführt.
(n = Größe der Eingabe, c = etwas Konstante)
Hier ist das Modelldiagramm, das die Big-O-Komplexität einiger Funktionen darstellt
prost :-)
graph Credits http://bigocheatsheet.com/
Plus für weniger Worte und mehr Klarheit. – user3144836
Ich habe alle Ihre illions. – Josephine
k^1000 ist außergewöhnlich groß, wenn k deutlich größer als 1 ist. Wenn k = 1, ist es weniger beeindruckend, und wenn k = 1.00069387 ..., ist es 2. – Josephine
@josephine, das ist wahr. – hvgotcodes