Landau-Symbole

Die Big-O-Notation ist eine Möglichkeit, Algorithmen zu vergleichen. Sie vergleicht sie, indem sie berechnet, wie viel Speicherplatz benötigt wird und wie viel Zeit für die Ausführung benötigt wird.

Die Big-O-Notation wird oft verwendet, um zu ermitteln, wie komplex ein Problem ist, auch bekannt als die Komplexitätsklasse des Problems. Der Mathematiker Paul Bachmann (1837-1920) war der erste, der diese Notation 1896 in der zweiten Auflage seines Buches "Analytische Zahlentheorie" verwendete. Edmund Landau (1877-1938) machte die Notation populär. Aus diesem Grund spricht man, wenn man von einem Landau-Symbol spricht, von dieser Notation.

Die Big-O-Notation ist nach dem Begriff "Ordnung der Funktion" benannt, der sich auf das Wachstum der Funktionen bezieht. Die Big-O-Notation wird verwendet, um die obere Grenze (den höchstmöglichen Betrag) der Wachstumsrate der Funktion zu finden, d.h. es wird die längste Zeit berechnet, die benötigt wird, um die Eingabe in die Ausgabe umzuwandeln. Das bedeutet, dass ein Algorithmus danach gruppiert werden kann, wie lange er in einem Worst-Case-Szenario, bei dem jedes Mal der längste Weg genommen wird, dauern kann.

Big O ist ein Ausdruck, der die Worst-Case-Szenario-Laufzeit findet und zeigt, wie effizient ein Algorithmus ist, ohne dass das Programm auf einem Computer ausgeführt werden muss. Dies ist auch nützlich, da verschiedene Computer unterschiedliche Hardware haben können und daher unterschiedlich viel Zeit für die Ausführung benötigen. Da Big O immer den ungünstigsten Fall annimmt, kann es eine konsistente Messung der Geschwindigkeit zeigen: Unabhängig von Ihrer Hardware wird O ( 1 ) {\darstellungsstil O(1)} $O(1)$ immer schneller fertig als O ( n ! ) {\darstellungsstil O(n!)} $O(n!)$ , weil sie unterschiedlich effizient sind.

Beispiele

Die folgenden Beispiele verwenden alle in Python geschriebenen Code. Beachten Sie, dass dies keine vollständige Liste der Big-O-Typen ist.

Konstante

O ( 1 ) {\Anzeigestil O(1)} $O(1)$ . Nimmt unabhängig von der Eingabe immer die gleiche Zeit in Anspruch. Nehmen Sie zum Beispiel eine Funktion, die eine ganze Zahl (genannt x) akzeptiert und den doppelten Wert zurückgibt:

def double(x): return x * 2 #Wiedergabe des Wertes von x mal 2

Nach dem Akzeptieren der Eingabe macht diese Funktion immer einen Schritt, um eine Ausgabe zurückzugeben. Sie ist konstant, weil sie immer die gleiche Zeit benötigt, also O ( 1 ) {\darstellungsstil O(1)} $O(1)$ .

Linear

O ( n ) {\Anzeigestil O(n)} $O(n)$ . Erhöht sich entsprechend der Größe der Eingabe, dargestellt durch n {\Darstellungsstil n} . Nehmen wir an, eine Funktion akzeptiert n und gibt jede Zahl von 1 bis n zurück:

def count(n): i = 1 #Erzeugen Sie einen Zähler namens "i" mit einem Wert von 1, während i <= n: #Während i kleiner oder gleich n ist print(i) #Drucken Sie den Wert von i i = i + 1 #Definieren Sie i als "den Wert von i + 1".

Wenn wir den Wert von 5 eingeben würden, dann würde dies 1 , 2 , 3 , 4 , 5 {\darstellungsstil 1,2,3,4,5} ausgeben $1,2,3,4,5$ , für deren Abschluss 5 Schleifen erforderlich sind. In ähnlicher Weise würde bei Eingabe von 100 die Ausgabe 1 , 2 , 3...98 , 99 , 100 {\darstellungsstil 1,2,3...98,99,100} $1,2,3...98,99,100$ erfolgen, wobei 100 Schleifen zum Abschluss erforderlich wären. Wenn die Eingabe n {\Darstellungsstil n} ist, dann ist die Laufzeit des Algorithmus jedes Mal genau n {\Darstellungsstil n} Schleifen, also O ( n ) {\Darstellungsstil O(n)} $O(n)$ .

Factorial

O ( n ! ) {\darstellungsstil O(n!)} $O(n!)$ . Erhöhungen der faktoriellen Beträge, d.h. die benötigte Zeit nimmt mit der Eingabe massiv zu. Nehmen wir zum Beispiel an, wir möchten fünf Städte auf der ganzen Welt besuchen und alle möglichen Ordnungen (Permutationen) sehen. Ein Algorithmus, den wir mit Hilfe der Itertools-Bibliothek von Python schreiben könnten, lautet wie folgt:

itertools importieren #Importieren Sie die itertools-Bibliotheksstädte = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rom'] #Ein Array mit den von uns ausgewählten Städten def Permutationen(Städte): #Ein Array von Städten als Eingabe nehmen: for i in itertools. permutations(cities): #Für jede Permutation unserer Artikel (der Variablen "i" zugeordnet) print(i) #Ausgabe i

Dieser Algorithmus berechnet jede einzelne Permutation unserer Städte und gibt sie dann aus. Beispiele für die Ausgabe werden sein:

('London', 'Paris', 'Berlin', 'Amsterdam', 'Rom') ('London', 'Paris', 'Berlin', 'Rom', 'Amsterdam') ('London', 'Paris', 'Amsterdam', 'Berlin', 'Rom') ('London', 'Paris', 'Amsterdam', 'Berlin', 'Rom') ... ("Rom", "Amsterdam", "Paris", "Berlin", "London") ("Rom", "Amsterdam", "Berlin", "London", "Paris") ("Rom", "Amsterdam", "Berlin", "Paris", "London")

Hier ist unsere Eingabeliste 5 Einträge lang, und für jede Auswahl verringern sich unsere verbleibenden Optionen um 1, d.h. unsere 5 Eingaben wählen 5 × 4 × 3 × 2 × 1 {\darstellungsstil 5\ mal 4\ mal 3\ mal 2\ mal 2\ mal 1} $5\times 4\times 3\times 2\times 1$ Einträge (oder 5 ! {\darstellungsstil 5!} $5!$ ). Wenn unsere Eingabe n {\Anzeigestil n} Städte lang ist, dann ist die Anzahl der Ausgaben n ! Mit $n!$ anderen Worten: Angenommen, wir gehen jede Permutation durch, dann benötigen wir O ( n ! ) {\darstellungsstil O(n!)} $O(n!)$ Schleifen, um sie zu vervollständigen.

Little-o-Notation

Eine strengere Version des großen O ist wenig-o. Der Unterschied zwischen Big O und little-o besteht darin, dass little-o eine strenge Obergrenze darstellt: Während O ( n ) {\Darstellungsstil O(n)} $O(n)$ bedeutet, dass die Fertigstellungszeit aufgrund der Eingabegröße auf dieses Maximum ansteigt, bedeutet das o ( n ) {\Darstellungsstil o(n)} $o(n)$ , dass die Fertigstellungszeit im Allgemeinen unter dieser Zeitspanne liegt. Mit anderen Worten, Big O nimmt an, dass jede Schleife den längsten Weg nimmt und der Prozess so lange wie möglich dauert, während little-o die tatsächlichen Laufzeiten realistischer einschätzt; wenn die Anzahl der Schleifen auf dem Wurf eines 6-seitigen Würfels basiert, nimmt Big O immer an, dass eine 6 gewürfelt wird, während little-o die gleiche Wahrscheinlichkeit berücksichtigt, dass andere Zahlen gewürfelt werden.

Fragen und Antworten

F: Was ist die Big-O-Notation?

A: Die Big O-Notation ist eine Methode zum Vergleich der Wachstumsraten verschiedener Funktionen. Sie wird häufig verwendet, um die Effizienz verschiedener Algorithmen zu vergleichen, indem berechnet wird, wie viel Speicherplatz und Zeit für die Ausführung benötigt wird. Sie kann auch verwendet werden, um zu ermitteln, wie komplex ein Problem ist.

F: Wer war der erste, der diese Notation verwendet hat?

A: Der Mathematiker Paul Bachmann (1837-1920) war der erste, der diese Notation in seinem Buch "Analytische Zahlentheorie" im Jahr 1896 verwendete.

F: Wofür steht das große O?

A: Big O steht für "Ordnung der Funktion", was sich auf die Wachstumsrate von Funktionen bezieht.

F: Wie wird Big O verwendet?

A: Die Big O-Notation wird verwendet, um eine obere Schranke (den höchstmöglichen Wert) für die Wachstumsrate der Funktion zu finden, d.h. sie berechnet die längste Zeit, die benötigt wird, um eine Eingabe in eine Ausgabe zu verwandeln. Das bedeutet, dass Algorithmen danach gruppiert werden können, wie lange sie im schlimmsten Fall brauchen, wobei jedes Mal der längste Weg genommen wird.

F: Was sind Landau-Symbole?

A: Landau-Symbole beziehen sich auf die Big O-Notation, benannt nach Edmund Landau (1877-1938), der diese Notation populär gemacht hat.

F: Warum ist Big O nützlich?

A: Big O ermöglicht es uns, die Geschwindigkeit zu messen, ohne Programme auf Computern laufen lassen zu müssen, da es immer von Worst-Case-Szenarien ausgeht und somit unabhängig von Hardwareunterschieden zwischen Computern konsistent ist. Es zeigt auch, wie effizient ein Algorithmus ist, ohne dass er tatsächlich auf einem Computer ausgeführt werden muss.