Big O-Notation mit Beispielen erklärt

Die Big O-Notation beschreibt die Geschwindigkeit oder Komplexität eines bestimmten Algorithmus. Wenn Ihr aktuelles Projekt einen vordefinierten Algorithmus erfordert, ist es wichtig zu verstehen, wie schnell oder langsam es im Vergleich zu anderen Optionen ist.

Was ist die Big O-Notation und wie funktioniert sie?

Einfach ausgedrückt, die Big O-Notation gibt an, wie viele Operationen ein Algorithmus ausführen wird. Es hat seinen Namen vom wörtlichen "Big O" vor der geschätzten Anzahl von Operationen.

Was Ihnen die Big O-Notation nicht sagt, ist die Geschwindigkeit des Algorithmus in Sekunden. Es gibt viel zu viele Faktoren, die die Ausführungszeit eines Algorithmus beeinflussen. Stattdessen verwenden Sie die Big O-Notation, um verschiedene Algorithmen anhand der Anzahl der durchgeführten Operationen zu vergleichen.

Big O legt eine Worst-Case-Laufzeit fest

Stellen Sie sich vor, Sie sind Lehrer mit einer Schülerin namens Jane. Sie möchten ihre Aufzeichnungen finden und verwenden einen einfachen Suchalgorithmus, um die Datenbank Ihres Schulbezirks zu durchsuchen.

Sie wissen, dass die einfache Suche O (n) Mal dauert. Dies bedeutet, dass Sie im schlimmsten Fall jeden einzelnen Datensatz (dargestellt durch n) durchsuchen müssen, um Jane's zu finden.

Wenn Sie jedoch die einfache Suche ausführen, stellen Sie fest, dass Janes Datensätze der allererste Eintrag in der Datenbank sind. Sie müssen sich nicht jeden Eintrag ansehen - Sie haben ihn beim ersten Versuch gefunden.

Hat dieser Algorithmus O (n) Zeit gebraucht? Oder hat es O (1) Zeit gedauert, weil Sie Janes Aufzeichnungen beim ersten Versuch gefunden haben?

In diesem Fall ist 0 (1) das beste Szenario - Sie hatten Glück, dass Janes Aufzeichnungen ganz oben standen. Die Big O-Notation konzentriert sich jedoch auf das Worst-Case-Szenario, das für eine einfache Suche 0 (n) ist. Es ist eine Bestätigung, dass die einfache Suche niemals langsamer als die O (n) -Zeit sein wird.

Die Laufzeit des Algorithmus wächst unterschiedlich schnell

Angenommen, es dauert 1 Millisekunde, um jedes Element in der Datenbank des Schulbezirks zu überprüfen.

Wenn Sie bei einfacher Suche 10 Einträge überprüfen müssen, dauert die Ausführung 10 ms. Mit dem binären Suchalgorithmus müssen Sie jedoch nur 3 Elemente überprüfen, was 3 ms dauert.

In den meisten Fällen enthält die Liste oder Datenbank, die Sie durchsuchen müssen, Hunderte oder Tausende von Elementen.

Wenn 1 Milliarde Elemente vorhanden sind, dauert die einfache Suche bis zu 1 Milliarde ms oder 11 Tage. Andererseits dauert die Verwendung der binären Suche im schlimmsten Fall nur 32 ms:

Offensichtlich wachsen die Laufzeiten für einfache Suche und binäre Suche nicht annähernd gleich schnell. Je größer die Liste der Einträge wird, desto länger dauert die binäre Suche. Die Laufzeit der einfachen Suche wächst exponentiell, wenn die Liste der Einträge zunimmt.

Aus diesem Grund ist es so wichtig zu wissen, wie sich die Laufzeit im Verhältnis zur Listengröße erhöht. Und genau hier ist die Big O-Notation so nützlich.

Die Big O-Notation zeigt die Anzahl der Operationen an

Wie oben erwähnt, zeigt die Big O-Notation nicht die Zeit an, zu der ein Algorithmus ausgeführt wird. Stattdessen wird die Anzahl der ausgeführten Operationen angezeigt. Hier erfahren Sie, wie schnell ein Algorithmus wächst, und können ihn mit anderen vergleichen.

Hier sind einige gängige Algorithmen und ihre Laufzeiten in Big O-Notation:

Big O-NotationBeispielalgorithmus
O (log n)Binäre Suche
Auf)Einfache Suche
O (n * log n)Schnelle Sorte
O (n2)Auswahl sortieren
Auf!)Reisender Verkäufer

Jetzt wissen Sie genug, um mit der Big O-Notation gefährlich zu sein. Gehen Sie raus und vergleichen Sie die Algorithmen.