Big O Notation - Einfach mit Abbildungen und Video erklärt

Die Big O-Notation wird verwendet, um zu kommunizieren, wie schnell ein Algorithmus ist. Dies kann wichtig sein, wenn Sie die Algorithmen anderer Personen und Ihre eigenen bewerten! In diesem Artikel erkläre ich die Big O-Notation und gebe Ihnen eine Liste der häufigsten Laufzeiten für Algorithmen, die sie verwenden.

Die Laufzeit des Algorithmus wächst unterschiedlich schnell

Mein Sohn Judah hat viele Spielsachen. Tatsächlich hat er eine Milliarde Spielzeuge erworben! Sie wären überrascht, wie schnell ein Kind so viele Spielsachen bekommen kann, wenn es das erste Enkelkind auf beiden Seiten der Familie ist. ??

Wie auch immer, Juda hat ein Problem. Wenn seine Freunde ein bestimmtes Spielzeug besuchen und mit ihm spielen möchten, kann es FÜR IMMER dauern, bis das Spielzeug gefunden ist. Deshalb möchte er einen Suchalgorithmus erstellen, mit dem er so schnell wie möglich ein bestimmtes Spielzeug finden kann. Er versucht sich zwischen zwei verschiedenen Suchalgorithmen zu entscheiden: einfache Suche und binäre Suche. (Machen Sie sich keine Sorgen, wenn Sie mit diesen Algorithmen nicht vertraut sind.)

Der gewählte Algorithmus muss schnell und korrekt sein. Einerseits ist die binäre Suche schneller. Und Judah hat oft nur etwa 30 Sekunden Zeit, bevor es seinem Freund langweilig wird, nach einem Spielzeug zu suchen. Andererseits ist ein einfacher Suchalgorithmus einfacher zu schreiben und es besteht eine geringere Wahrscheinlichkeit, dass Fehler auftreten. Es wäre sicher peinlich, wenn sein Freund Fehler in seinem Code finden würde! Um besonders vorsichtig zu sein, beschließt Judah, beide Algorithmen mit einer Liste von 100 Spielzeugen zu planen.

Nehmen wir an, es dauert 1 Millisekunde, um ein Spielzeug zu überprüfen. Bei der einfachen Suche muss Judah 100 Spielzeuge überprüfen, sodass die Suche 100 ms dauert. Andererseits muss er nur 7 Spielzeuge mit binärer Suche überprüfen (log2 100 ist ungefähr 7, keine Sorge, wenn diese Mathematik verwirrend ist, da dies nicht der Hauptpunkt dieses Artikels ist), sodass die Suche 7 ms dauert laufen. Aber wirklich, die Liste wird eine Milliarde Spielzeuge enthalten. Wenn ja, wie lange dauert die einfache Suche? Wie lange dauert die binäre Suche?

Laufzeit für einfache Suche vs. binäre Suche mit einer Liste von 100 Elementen

Judah führt eine binäre Suche mit 1 Milliarde Spielzeugen durch und es dauert 30 ms (log2 1.000.000.000 sind ungefähr 30). "32 ms!" er denkt. „Die binäre Suche ist ungefähr 15-mal schneller als die einfache Suche, da die einfache Suche 100 ms mit 100 Elementen und die binäre Suche 7 ms dauerte. Eine einfache Suche dauert also 30 × 15 = 450 ms, oder? Weit unter den 30 Sekunden, die mein Freund braucht, um sich zu langweilen. “ Juda beschließt, einfach zu suchen. Ist das die richtige Wahl?

Es stellte sich heraus, dass Juda sich geirrt und einen Freund fürs Leben verloren hat. ? Die Laufzeit für die einfache Suche mit 1 Milliarde Elementen beträgt 1 Milliarde ms, was 11 Tagen entspricht! Das Problem ist, dass die Laufzeiten für die binäre Suche und die einfache Suche nicht mit der gleichen Geschwindigkeit wachsen.

Die Laufzeiten wachsen mit sehr unterschiedlichen Geschwindigkeiten! Mit zunehmender Anzahl von Elementen dauert die Ausführung der binären Suche etwas länger, die einfache Suche jedoch viel länger. Wenn die Liste der Zahlen größer wird, wird die binäre Suche plötzlich viel schneller als die einfache Suche.

Judah hat sich also geirrt, dass die binäre Suche immer 15-mal schneller ist als die einfache Suche. Wenn es 1 Milliarde Spielzeuge gibt, ist es eher 33 Millionen Mal schneller.

Es ist sehr wichtig zu wissen, wie sich die Laufzeit mit zunehmender Listengröße erhöht. Hier kommt die Big O-Notation ins Spiel.

Die Big O-Notation gibt an, wie schnell ein Algorithmus ist. Angenommen, Sie haben eine Liste der Größe n . Bei der einfachen Suche muss jedes Element überprüft werden, sodass n Operationen erforderlich sind. Die Laufzeit in Big O-Notation ist O ( n ).

Wo sind die Sekunden? Es gibt keine - Big O sagt Ihnen die Geschwindigkeit nicht in Sekunden. Mit der Big O-Notation können Sie die Anzahl der Operationen vergleichen. Hier erfahren Sie, wie schnell der Algorithmus wächst.

Lassen Sie uns ein weiteres Beispiel machen. Die binäre Suche erfordert log n- Operationen, um eine Liste der Größe n zu überprüfen . Was ist die Laufzeit in Big O-Notation? Es ist O (log n ). Im Allgemeinen wird die Big O-Notation wie folgt geschrieben.

Hier erfahren Sie, wie viele Operationen ein Algorithmus ausführen wird. Es wird als Big O-Notation bezeichnet, da Sie vor der Anzahl der Operationen ein „Big O“ setzen.

Big O legt eine Worst-Case-Laufzeit fest

Angenommen, Sie verwenden eine einfache Suche, um nach einem Benutzer in Ihrer Benutzerdatenbank zu suchen. Sie wissen, dass die einfache Suche O ( n ) Zeit benötigt, was bedeutet, dass Ihr Algorithmus im schlimmsten Fall jeden Benutzer in der Datenbank durchsuchen muss. In diesem Fall suchen Sie einen Benutzer mit dem Namen 'aardvark213'. Dies ist der erste Benutzer in der Liste. Ihr Algorithmus musste also nicht jeden Eintrag betrachten - er fand ihn beim ersten Versuch. Hat der Algorithmus O ( n ) Zeit gebraucht? Oder hat es O (1) Zeit gedauert, weil es die Person beim ersten Versuch gefunden hat?

Die einfache Suche dauert immer noch O ( n ) Zeit. In diesem Fall hat der Algorithmus sofort gefunden, wonach er gesucht hat. Das ist das beste Szenario. Bei der Big O-Notation handelt es sich jedoch um das Worst-Case- Szenario. Sie können also sagen, dass der Algorithmus im schlimmsten Fall jeden Benutzer in der Datenbank einmal durchsuchen muss. Das ist O ( n ) Zeit. Es ist eine Beruhigung - Sie wissen, dass die einfache Suche niemals langsamer als O ( n ) sein wird.

Einige gängige Big O-Laufzeiten

Hier sind fünf Big O-Laufzeiten, auf die Sie häufig stoßen werden, sortiert von der schnellsten zur langsamsten:

  • O (log n ), auch als log time bezeichnet. Beispiel: Binäre Suche.
  • O ( n ), auch als lineare Zeit bekannt . Beispiel: Einfache Suche.
  • O ( n * log n ). Beispiel: Ein schneller Sortieralgorithmus wie Quicksort.
  • O ( n 2). Beispiel: Ein langsamer Sortieralgorithmus wie die Auswahlsortierung.
  • O ( n !). Beispiel: Ein sehr langsamer Algorithmus wie der reisende Verkäufer.

Visualisierung verschiedener Big O-Laufzeiten

Angenommen, Sie zeichnen ein Raster mit 16 Feldern und können dazu aus 5 verschiedenen Algorithmen auswählen. Wenn Sie den ersten Algorithmus verwenden, benötigen Sie O (log n ) Zeit, um das Raster zu zeichnen. Sie können 10 Operationen pro Sekunde ausführen. Mit der Zeit O (log n ) benötigen Sie 4 Operationen, um ein Raster von 16 Feldern zu zeichnen (log 16 Basis 2 ist 4). Das Zeichnen des Gitters dauert also 0,4 Sekunden. Was ist, wenn Sie 1.024 Kartons zeichnen müssen? Sie benötigen 1.024 = 10 Vorgänge oder 1 Sekunde, um ein Raster mit 1.024 Feldern zu zeichnen. Diese Zahlen verwenden den ersten Algorithmus.

Der zweite Algorithmus ist langsamer: Es dauert O ( n ) Zeit. Es werden 16 Operationen benötigt, um 16 Kisten zu zeichnen, und es werden 1.024 Operationen benötigt, um 1.024 Kisten zu zeichnen. Wie viel Zeit ist das in Sekunden?

So lange würde es dauern, ein Raster für den Rest der Algorithmen zu zeichnen, vom schnellsten zum langsamsten:

Es gibt auch andere Laufzeiten, aber dies sind die fünf häufigsten.

Dies ist eine Vereinfachung. In der Realität kann man nicht so ordentlich von einer Big O-Laufzeit in eine Reihe von Operationen konvertieren, aber dies ist eine gute Schätzung.

Fazit

Hier sind die wichtigsten Imbissbuden:

  • Die Geschwindigkeit des Algorithmus wird nicht in Sekunden gemessen, sondern im Wachstum der Anzahl der Operationen.
  • Stattdessen sprechen wir darüber, wie schnell sich die Laufzeit eines Algorithmus mit zunehmender Größe der Eingabe erhöht.
  • Die Laufzeit von Algorithmen wird in Big O-Notation ausgedrückt.
  • O (log n ) ist schneller als O ( n ), aber es wird viel schneller, wenn die Liste der Elemente, die Sie suchen, wächst.

Und hier ist ein Video, das viel von dem, was in diesem Artikel steht, und mehr abdeckt.

Ich hoffe, dieser Artikel hat Ihnen mehr Klarheit über die Big O-Notation gebracht. Dieser Artikel basiert auf einer Lektion in meinem Videokurs von Manning Publications mit dem Titel Algorithms in Motion. Der Kurs basiert auf dem erstaunlichen Buch Grokking Algorithms von Adit Bhargava. Er ist derjenige, der alle lustigen Illustrationen in diesem Artikel gezeichnet hat.

Wenn Sie am besten durch Bücher lernen, holen Sie sich das Buch! Wenn Sie am besten durch Videos lernen, sollten Sie meinen Kurs kaufen. Mit dem Code ' 39carnes ' erhalten Sie 39% Rabatt auf meinen Kurs .