Big-O-Notation: Zeitkomplexität mithilfe von Flussdiagrammen verstehen

Ich kann Edisons Beitrag zur Big-O-Komplexität in JavaScript wärmstens empfehlen. Es ist der freundlichste Artikel, den ich zu diesem Thema gesehen habe.

Artikel nicht mehr verfügbar

Ich werde hier Punkte von Edison übernehmen, während ich die Zeitkomplexität von Big-O mit Flussdiagrammen visualisiere.

O log(n)

Logarithmische Zeit

Die Art und Weise, wie ich Zeitkomplexität visuell verstehe, besteht darin, mir den Iterator, zum Beispiel i*2, anzusehen und zu sehen, wie viele Schleifen die Funktion hat.

An)

Lineare Zeit



Lineare Zeit und logarithmische Zeit sehen ähnlich aus, die Ausgabe unterscheidet sich jedoch aufgrund der Bedingungen der Schleife. exampleLogarithmic(100) gibt 1, 2, 4, 8, 16, 32, 64 zurück, während exampleLinear(100) einfach alle positiven Ganzzahlen unter 100 durchläuft.

O(n^2)

Quadratische Zeit



Die Anzahl der Schleifen stimmt mit dem Exponenten überein, auf den n erhöht wird. Sie können buchstäblich sehen, wie die Funktion mit zunehmender Zeitkomplexität größer wird.

O(n^3)

Kubische Zeit



Dies ist nicht die einzige Möglichkeit, die Zeitkomplexität zu verstehen, aber es ist wirklich hilfreich, buchstäblich zu sehen, wie die Funktion mit zunehmender Zeitkomplexität länger wird. Manchmal wird in Schwarzweiß geschriebener Code <pre> Blöcke vermitteln visuellen Lernenden den Sinn nicht.

Jetzt machen wir ein Quiz. Wie hoch ist die zeitliche Komplexität dieser Funktion?

Machen Sie Ihre Vermutung...



Es ist linear! Das kann ich erkennen, weil es eine Schleife gibt und der Iterator nicht dazu führt, dass die Schleife irgendwelche Ganzzahlen überspringt.

Wie hoch ist die zeitliche Komplexität dieser Funktion?



Zweifle nicht an dir. Obwohl sich dies ein wenig von den ersten Beispielen unterscheidet, weist es eine lineare Zeitkomplexität auf.

Wie hoch ist die zeitliche Komplexität dieser Funktion?



Möglicherweise sehen Sie hier ein Muster. Es ist linear!

Wenn Sie meiner Logik gefolgt sind, könnte dies eine Fangfrage sein:

Ich sagte, dass die Anzahl der Schleifen, die der Exponent n bezeichnet, erhöht wird. Warum hat dies also eine lineare Zeitkomplexität und nicht eine quadratische?

Dies hätte eine quadratische Zeitkomplexität, wenn eine for-Schleife innerhalb einer anderen for-Schleife angezeigt würde. Allerdings hat eine for-Schleife, die nach einer anderen for-Schleife läuft, keine quadratische, sondern eher eine lineare Zeitkomplexität.

Okay, wie hoch ist also die zeitliche Komplexität dieser Funktion?



Hier gibt es nichts Schwieriges. Dies hat eine quadratische Zeitkomplexität.

Nun zu Ihrer letzten Frage – eine Frage, die alle anderen Fragen in Frage stellt – wie hoch ist die zeitliche Komplexität dieser Funktion?



Ich hoffe, Sie sehen sich die Bedingungen der for-Schleife sowie die schiere Anzahl der Schleifen an. Dies hat aufgrund der Schleifenbedingung i<n*n.

eine quadratische Zeitkomplexität

Die Bilder in diesem Beitrag habe ich mit meiner App generiert, deren Entwicklungsprozess ich in einem anderen Beitrag beschrieben habe:

[

So erreichen Sie 100 bei Lighthouse

Ender Minyard ・ 30. August 2020 ・ 2 Minuten Lesezeit

webperf#speed#javascript#webdev

](/ender_minyard/how-i-got-100-on-lighthouse-2icd)

Das obige ist der detaillierte Inhalt vonBig-O-Notation: Zeitkomplexität mithilfe von Flussdiagrammen verstehen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!