Es ist oft notwendig zu verstehen, wie effektiv der Code geschrieben wird. Dabei ist es üblich, die Zeit der Implementierung und/oder den beobachteten Speicher zu bewerten.
Asymptotische Komplexität wird oft verwendet, um diese Bewertung auszudrücken (nachstehend gehen wir davon aus, dass es keine Zeit im Vergleich zu Gedächtnis signifikanter Unterschiede gibt)
Die Komplexität hängt von variablen Eingangsparametern ab und beschreibt sie in Abhängigkeit von der Größe der Daten (Detail im Beispiel am Ende der Theorie).
Um die Komplexität zu bewerten, sind wir neugierig auf das asymptotische Verhalten dieser Funktionen (von hier und der kurze Ausdruck ist "cod asymptomy"), das heißt, wenn die Eingabedaten recht groß sind.
Deshalb verwenden sie die sogenannte O-Notation. Es ist nicht die einfachste mathematische Theorie, in die wir nicht gehen. Weitere Informationen
Wikipediaoder andere Internet-Ressourcen.
Es muss jedoch daran erinnert werden, dass der Code asymptotisch in dieser sehr nodule fast immer angegeben ist, also ist es immer wert, es zu tun. Wir werden herausfinden, wie es in ein wenig zu tun.
Wie aus dem Namen ersichtlich, werden die Funktionen innerhalb der von einem großen "O" markierten Boxen aufgezeichnet. Zum Beispiel: O(n), O(nm), O(log(c)), wobei wir als n, m, c oder anderes die mögliche Größe der Eingabedaten identifizieren.
Es geht darum, wie die Asymptotik ist.
(1) Zunächst müssen wir die Größe der Daten verstehen, die der Zeitpunkt des Programms abhängt. Vergleiche die Größe dieser Daten mit Variablen, in denen Asymptotik berechnet werden soll. Sie sind in der Regel durch Buchstaben n und dann m gekennzeichnet.
(2) Dann werden wir die wirkliche Zeit der Arbeit durch diese Variablen zeigen. Wenn einige Teile schwer zu zählen sind, werden sie geschätzt, um und höher zu sein (d.h. übertrieben mit einer Reserve), d.h., dass das Programm mehr Ressourcen ausgibt, als es tatsächlich nicht beängstigend ist, aber die umgekehrte Situation kann möglicherweise Probleme verursachen.
(3) Danach nehmen wir den härtesten Teil aller Urteile. Es kann einige geben, wenn sie nicht verglichen werden können (z.B. verschiedene Variablen, d.h. Größe verschiedener Eingänge, weil wir nicht im Voraus wissen, was das Programm am Eingang erhalten wird). Anschließend werden konstante Multiplikatoren abgesenkt (auch wenn sie zunächst beispielsweise 100.000n oder 0,00001n, nur n) waren und dann in den O-Notationen aufgezeichnet.
Wir werden ein kleines Beispiel herausfinden.
Sagen wir, wir haben ein Programm, das eine Reihe von Zahlen am Eingang akzeptiert und die Menge der Austausche, die benötigt werden, um die Blase dieser Masse zu sortieren und die Fusion zu sortieren.
Hier hängt die Zeit des Programms nur vom Eingang ab. Wir geben ihm seine Größe.
Wir schauen uns die richtige Zeit der Arbeit an. n's terations to read the mass, a bubble that will be used im schlimmsten von n*(n-1)/2 Wechselkursen (dies ist der schlimmste Fall, den wir berücksichtigen müssen), eine Verschmelzung, die schwierig zu bewerten ist, aber wir werden es oben als 10*n*log(n) schätzen (d.h. wir wissen, dass es für O(n) funktioniert
Geschätzte Gesamtarbeitszeit: n + n*(n-1)/2 + 10*n*log(n) = n + n + n^2/2 - n/2 + 10*n*log(n). Es ist durchaus verständlich, dass die 1. und 3. davon nicht entscheidend sind. Die einzige Frage ist "heavy", zwei oder vier.
Wir weisen darauf hin, dass mit einem kleinen n, z.B. n=4, der 4. wichtiger ist als der 2. (8 gegen 80). Dies hat jedoch nichts mit der Tatsache zu tun, dass wir eine asymptotische Analyse durchführen, was darauf hindeutet, dass die Eingabedaten recht groß sind, beispielsweise n=1000000. Auf dieser Ebene der Eingabedaten ist bereits klar, wie n^2/2 tatsächlich 10*n*log(n) überschreitet.
Am Ende haben wir die härteste n^2/2 verlassen und jetzt ignorieren wir seinen konstanten Multiplikator 1/2. Die Asymmetrie dieses Algorithmus ist also gleich O(n^2).
Es ist zu verstehen, dass selbst eine asymptotische Konstante keine Rolle spielt, es ist wichtig im realen Leben, so ist es auch wichtig, die genaue Zeit der Arbeit zu bewerten, da manchmal ist es vorteilhafter, Algorithmus mit einer größeren Asymptomie zu wählen, weil es immer schneller auf realen Daten sein kann. Dies ist minus asymptotische Analyse: Es wird angenommen, dass der Wert der Variablen auf Unendlichkeit eager ist, und am Ende nimmt eine Funktion größere Bedeutung als die andere an, mit so großen Werten, dass es im realen Leben nicht sein kann. Aber in der Praxis sind solche Fälle sehr selten.