Wie lautet eine einfache englische Erklärung der "Big O"-Notation?

Question

Ich bevorzuge so wenig formale Definitionen wie möglich und einfache Mathematik.

Answer 1

Die Big-O-Schreibweise wird von Programmierern meist als Näherungswert dafür verwendet, wie lange eine Berechnung (ein Algorithmus) in Abhängigkeit von der Größe der Eingabemenge dauert.

Big O ist nützlich, um zu vergleichen, wie gut zwei Algorithmen skalieren, wenn die Anzahl der Eingaben erhöht wird.

Genauer gesagt Big-O-Notation wird verwendet, um das asymptotische Verhalten einer Funktion auszudrücken. Das heißt, wie sich die Funktion verhält, wenn sie sich dem Unendlichen nähert.

In vielen Fällen wird das "O" eines Algorithmus in einen der folgenden Fälle fallen:

• O(1) - Die Zeit bis zur Fertigstellung ist unabhängig von der Größe der Eingabemenge gleich lang. Ein Beispiel ist der Zugriff auf ein Array-Element nach Index.
• O(Log N) - Die Zeit bis zur Fertigstellung steigt ungefähr mit log2(n). Beispielsweise dauert die Suche nach 1024 Einträgen etwa doppelt so lange wie die Suche nach 32 Einträgen, da Log2(1024) = 10 und Log2(32) = 5 ist. Ein Beispiel ist die Suche nach einem Element in einer binärer Suchbaum (BST).
• O(N) - Zeit bis zur Fertigstellung, die linear mit der Größe der Eingabemenge skaliert. Mit anderen Worten, wenn Sie die Anzahl der Elemente in der Eingabemenge verdoppeln, dauert der Algorithmus etwa doppelt so lange. Ein Beispiel ist das Zählen der Anzahl der Elemente in einer verknüpften Liste.
• O(N Log N) - Die Zeit bis zum Abschluss erhöht sich um die Anzahl der Elemente mal das Ergebnis von Log2(N). Ein Beispiel hierfür ist Haufensortierung y schnelle Sortierung .
• O(N^2) - Die Zeit bis zur Fertigstellung ist ungefähr gleich dem Quadrat der Anzahl der Aufgaben. Ein Beispiel hierfür ist Blasensortierung .
• O(N!) - Die Zeit bis zur Fertigstellung ist der Faktor der Eingabemenge. Ein Beispiel hierfür ist die Reisende-Verkäufer-Problem Brute-Force-Lösung .

Big O ignoriert Faktoren, die nicht in sinnvoller Weise zur Wachstumskurve einer Funktion beitragen, wenn die Eingabegröße gegen unendlich ansteigt. Das bedeutet, dass Konstanten, die zur Funktion addiert oder mit ihr multipliziert werden, einfach ignoriert werden.

Answer 2

Big O ist nur eine Möglichkeit, sich auf eine gängige Art und Weise auszudrücken: "Wie viel Zeit / Platz braucht es, um meinen Code auszuführen?".

Man sieht oft O(n), O(n 2 ), O(nlogn) und so weiter, all das sind nur Möglichkeiten zu zeigen: Wie ändert sich ein Algorithmus?

O(n) bedeutet, dass Big O gleich n ist, und jetzt werden Sie vielleicht denken: "Was ist n!?" Nun, "n" ist die Anzahl der Elemente. Stellen Sie sich vor, Sie wollen nach einem Element in einem Array suchen. Im schlimmsten Fall befindet sich das Element am letzten Index, was bedeutet, dass die Suche so viel Zeit in Anspruch nimmt, wie es Elemente in der Liste gibt, also sagen wir ganz allgemein: "Oh hey, n ist eine angemessene Anzahl von Werten!

Dann werden Sie vielleicht verstehen, was "n 2 " bedeutet, aber um noch konkreter zu werden, spielen Sie mit dem Gedanken, dass Sie einen einfachen, den einfachsten der Sortieralgorithmen haben; Bubblesort. Dieser Algorithmus muss die gesamte Liste nach jedem Element durchsuchen.

Meine Liste

1. 1
2. 6
3. 3

Der Ablauf wäre hier folgender:

• Vergleiche 1 und 6, was ist größer? Ok, 6 ist in der richtigen Position und bewegt sich nach vorne!
• Vergleiche 6 und 3, oh, 3 ist weniger! Lass uns das verschieben, ok die Liste hat sich geändert, wir müssen jetzt von vorne anfangen!

Dies ist O n 2 weil Sie alle Einträge in der Liste betrachten müssen, die aus "n" Einträgen besteht. Für jedes Element schauen Sie sich alle Elemente noch einmal an, um zu vergleichen, ist dies auch "n", so dass Sie für jedes Element "n" Mal schauen, was n*n = n bedeutet 2

Ich hoffe, das ist so einfach, wie Sie es sich wünschen.

Aber denken Sie daran: Big O ist nur eine Möglichkeit, sich selbst in Zeit und Raum zu erleben.

Answer 3

Big O beschreibt die grundlegende Skalierung eines Algorithmus.

Es gibt viele Informationen, die Big O Ihnen nicht über einen bestimmten Algorithmus mitteilt. Es gibt nur Informationen über die Skalierung eines Algorithmus, insbesondere darüber, wie der Ressourcenverbrauch (z. B. Zeit oder Speicher) eines Algorithmus in Abhängigkeit von der "Eingabegröße" skaliert.

Betrachten Sie den Unterschied zwischen einer Dampfmaschine und einer Rakete. Es handelt sich nicht nur um verschiedene Varianten derselben Sache (wie z. B. ein Prius-Motor im Vergleich zu einem Lamborghini-Motor), sondern sie sind im Kern völlig unterschiedliche Antriebssysteme. Eine Dampfmaschine mag schneller sein als eine Spielzeugrakete, aber kein Dampfkolbenmotor wird die Geschwindigkeiten einer Trägerrakete im Orbit erreichen. Das liegt daran, dass diese Systeme unterschiedliche Skalierungseigenschaften haben, was das Verhältnis des benötigten Treibstoffs ("Ressourcenverbrauch") zum Erreichen einer bestimmten Geschwindigkeit ("Inputgröße") angeht.

Warum ist das so wichtig? Weil Software mit Problemen zu tun hat, die sich in ihrer Größe um Faktoren von bis zu einer Billion unterscheiden können. Überlegen Sie sich das einen Moment lang. Das Verhältnis zwischen der Geschwindigkeit, die man braucht, um zum Mond zu reisen, und der menschlichen Gehgeschwindigkeit beträgt weniger als 10.000:1, und das ist absolut winzig im Vergleich zu der Bandbreite an Eingabegrößen, mit denen Software konfrontiert werden kann. Und da Software mit einer astronomischen Bandbreite an Eingabegrößen konfrontiert sein kann, besteht die Möglichkeit, dass die Big-O-Komplexität eines Algorithmus, also seine grundlegende Skalierungsnatur, alle Implementierungsdetails übertrumpft.

Betrachten Sie das Beispiel der kanonischen Sortierung. Bubble-Sortierung ist O(n 2 ), während Merge-Sortierung O(n log n) ist. Nehmen wir an, Sie haben zwei Sortieranwendungen, Anwendung A, die Bubble-Sort verwendet, und Anwendung B, die Merge-Sort verwendet, und nehmen wir an, dass bei Eingabegrößen von etwa 30 Elementen Anwendung A beim Sortieren 1.000x schneller ist als Anwendung B. Wenn Sie nie viel mehr als 30 Elemente sortieren müssen, ist es offensichtlich, dass Sie Anwendung A bevorzugen sollten, da sie bei diesen Eingabegrößen viel schneller ist. Wenn Sie jedoch feststellen, dass Sie vielleicht zehn Millionen Elemente sortieren müssen, dann ist Anwendung B in diesem Fall erwartungsgemäß Tausende Male schneller als Anwendung A, was ausschließlich auf die Art und Weise zurückzuführen ist, wie jeder Algorithmus skaliert.

Answer 4

Hier ist das einfache englische Bestiarium, das ich zu verwenden pflege, wenn ich die gängigen Big-O-Varianten erkläre

In allen Fällen sind Algorithmen, die weiter oben auf der Liste stehen, denjenigen vorzuziehen, die weiter unten auf der Liste stehen. Die Kosten für den Wechsel zu einer teureren Komplexitätsklasse sind jedoch sehr unterschiedlich.

O(1):

Kein Wachstum. Unabhängig davon, wie groß das Problem ist, kann man es in der gleichen Zeit lösen. Dies ist in gewisser Weise vergleichbar mit dem Rundfunk, bei dem die gleiche Energiemenge für die Übertragung über eine bestimmte Entfernung benötigt wird, unabhängig von der Anzahl der Personen, die sich im Sendebereich befinden.

O(log n ):

Diese Komplexität ist die gleiche wie O(1) Nur dass es noch ein bisschen schlimmer ist. Für alle praktischen Zwecke können Sie dies als eine sehr große konstante Skalierung betrachten. Der Unterschied im Arbeitsaufwand zwischen der Verarbeitung von 1.000 und 1 Milliarde Elementen beträgt nur den Faktor sechs.

O( n ):

Die Kosten für die Lösung des Problems sind proportional zur Größe des Problems. Wenn sich die Größe des Problems verdoppelt, verdoppeln sich auch die Kosten für die Lösung. Da die meisten Probleme auf irgendeine Weise in den Computer eingescannt werden müssen, z. B. durch Dateneingabe, Festplattenlesung oder Netzwerkverkehr, ist dies im Allgemeinen ein vertretbarer Skalierungsfaktor.

O( n Protokoll n ):

Diese Komplexität ist sehr ähnlich zu O( n ) . Für alle praktischen Zwecke sind die beiden gleichwertig. Dieser Grad an Komplexität würde im Allgemeinen noch als skalierbar angesehen werden. Wenn man die Annahmen etwas verändert O( n Protokoll n ) Algorithmen können umgewandelt werden in O( n ) Algorithmen. Durch die Begrenzung der Größe der Schlüssel wird beispielsweise die Sortierung von O( n Protokoll n ) zu O( n ) .

O( n 2 ):

Wächst als Quadrat, wobei n ist die Länge der Seite eines Quadrats. Dies ist die gleiche Wachstumsrate wie der "Netzwerkeffekt", bei dem jeder in einem Netzwerk jeden anderen im Netzwerk kennen könnte. Wachstum ist teuer. Die meisten skalierbaren Lösungen können Algorithmen mit diesem Komplexitätsgrad nicht verwenden, ohne dass es zu erheblichen Kunststücken kommt. Dies gilt im Allgemeinen für alle anderen polynomialen Komplexitäten - O( n k ) - auch.

O(2 n ):

Skaliert nicht. Sie haben keine Chance, ein Problem von nichttrivialer Größe zu lösen. Nützlich, um zu wissen, was zu vermeiden ist, und für Experten, um ungefähre Algorithmen zu finden, die in O( n k ) .

Answer 5

Big O ist ein Maß dafür, wie viel Zeit/Speicherplatz ein Algorithmus im Verhältnis zur Größe seiner Eingabe benötigt.

Wenn ein Algorithmus O(n) ist, dann wächst die Zeit/der Raum mit der gleichen Rate wie seine Eingabe.

Wenn ein Algorithmus O(n 2 ), dann wächst die Zeit/der Raum im Verhältnis zum Quadrat des Inputs.

und so weiter.