Landau-Symbole

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)} . 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:

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)} .

Linear

O ( n ) {\Anzeigestil 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:

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 , 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} 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)} .

Factorial

O ( n ! ) {\darstellungsstil 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:

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} Einträge (oder 5 ! {\darstellungsstil 5!} ). Wenn unsere Eingabe n {\Anzeigestil n} Städte lang ist, dann ist die Anzahl der Ausgaben n ! Mit anderen Worten: Angenommen, wir gehen jede Permutation durch, dann benötigen wir O ( n ! ) {\darstellungsstil O(n!)} Schleifen, um sie zu vervollständigen.

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)} bedeutet, dass die Fertigstellungszeit aufgrund der Eingabegröße auf dieses Maximum ansteigt, bedeutet das o ( n ) {\Darstellungsstil 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.