Die O Notation. Wie schnell ist dein Code?

Keylearnings:

• Die O Notation zur Messung der Performance eines Algorithmus.
• Was ist Komplexität?
• Was ist Performance?
• Was ist konstante Komplexität?
• Was ist lineare Komplexität?
• Was ist quadratische Komplexität?
• Was ist logarithmische Komplexität?
• Die Rechenregeln der O Notation.

Usain Bolt 9,6 Sekunden beim Sprintrennen über 100m bei der Leichtathletik WM in Berlin.

Anders Fannemel 251m bei der Skiflug WM in Vikasund.

Aleksei Lochchev 264kg. Neuer Weltrekord im Gewichtheben!

Wie schnell, wie weit, wie hoch geht’s bei dir?

Eine Frage, die du dir auch bei deinem Code stellen musst.

Aber nach welchem Maß können wir die Leistung unseres Codes beurteilen?

Genau das möchte ich in diesem Artikel beantworten und dir zeigen wie du mit der sogenannten groß O Notation die Performance deines Codes quantitativ bestimmen kannst.

Was ist Komplexität?

Warum hält Usain Bolt den Weltrekord im 100m Sprint ohne den Hauch einer Chance bei einem Marathonlauf zu haben?

Weil ein Marathonläufer Ausdauer benötigt wohingegen die Leistung eines Sprinters stark von der Muskelkraft abhängt.

Für beide Läufertypen sind unterschiedliche Ressourcen von Bedeutung.

Muskelkraft und Ausdauer sind aber gegenläufig.

Ein Ausdauerläufer muss möglichst leicht sein und kann deshalb nicht so viel Muskelmasse aufbauen wie ein Sprinter.

Und genau so ist es auch in deinem Programmcode.

Deine Programme benötigen keine Muskelkraft oder Ausdauer, dafür aber Speicher, Rechenleistung und Netzwerkbandbreite.

Die Menge der in Anspruch genommenen Ressourcen nennt man Programmkomplexität.

Um die Leistung eines Programms beurteilen zu können, muss zunächst entschieden werden, welche Ressource günstig und welche teuer ist.

Ein leistungsstarkes Programm geht schonend mit den teuren Ressourcen um.

Heute leben wir in einer Zeit, in der Speicher in großen Mengen günstig zu haben ist, deshalb ist die Rechenleistung die Ressource, die wir in der Regel schonen wollen.

Ähnlich wie der Marathonläufer eine bessere Ausdauer auf Kosten der Muskelkraft trainiert, können wir die Rechenleistung auf Kosten des Speicherbedarfs erhöhen indem wir beispielsweise mehrfach benötigte Zwischenergebnisse einer Rechnung zwischenspeichern.

Performance und Zeitkomplexität

Oft wird von der Performance einer Software gesprochen. Doch was bedeutet das?

Hier die Definition:

Die Performance ist die Zeitdauer, die ein Programm benötigt um eine bestimmte Aufgabe zu lösen.

So reichen Google knapp 0,7Sekunden um 154.000.000 Ergebnisse zu dem Suchwort Wetter zu finden. Was einer excellenten Performance entspricht.

Anstatt von Performance spricht man häufig auch von der Zeitkomplexität.

Eine höhere Performance erreichen wir vor allem durch Programme, die schonend mit der Ressource Rechenleistung umgehen.

Dabei ist klar, dass die Suche nach der Stecknadel im Heuhaufen mehr Zeit in Anspruch nimmt als das Auffinden eines Wolkenkratzers in einer Plattenbau-Siedlung.

Ein sinnvolles Maß für die Performance muss also in jedem Fall die Menge der Daten, die unser Programm verarbeitet berücksichtigen.

Wir machen uns das Leben leicht!

In einem Programm werden unterschiedliche Operationen durchgehführt.

Es besteht aus Zuweisungen, arithmetischen Operationen und Vergleichen, die unterschiedlich schnell durchgeführt werden.

So ist ein Vergleich bespielsweise schneller ausführbar als eine arithmetische Operation.

Diese Unterschiede werden bei der groß O Notation vernachlässigt. Es ist egal, ob ein Programm vermehrt (aufwendige) arithmetische Operationen oder besonders viele (einfache) Vergleiche ausführt.

Bei der groß O Notation interessiert uns nicht einmal die Gesamtanzahl der auszuführenden Operationen. Alles was zählt ist der Anstieg der Zeitkomplexität in Abhängig von der Größe der Eingabedaten.

Das hat auch den Vorteil, dass wir den Einfluss der Hardware, auf der unser Programm läuft vernachlässigen können.

Worst case, average case oder best case Betrachtung?

Schauen wir uns folgende Methode an:

1: public static int konstantKomplex(int suchelement){
2:   int[] elemente = {4,6,8,2,5,10,11,14,13,19,15,3,34,23,9,7,47,39,21,99};
3:   for(int i = 0;i<elemente.length;i++){
4:   if(elemente[i] == suchelement){
6:	return i;
7:     }
8:   }
9:   return -1;
10:}

Die Methode sucht in einem 20 elementigen Array nach dem im Parameter suchelement gespeicherten Wert und liefert dessen Array-Position zurück. Im Fall, dass das gesuchte Element nicht im Array enthalten ist, wird der Wert -1 zurück geliefert.

Mit welcher Laufzeit ist im besten, mittleren und im schlechtesten Fall zu rechnen?

Die Zeitkomplexität unseres Suchproblems hängt davon ab, an welcher Position das Element, welches wir suchen im Array gespeichert ist.

Im besten Fall befindet sich das gesuchte Element an erster Position. In diesem Fall benötigen wir nämlich nur einen einzigen Vergleich und sind fertig. Somit lässt sich in unserem Beispiel der Wert 4 am leichtesten finden.

Unser Suchproblem ist von mittlerer Zeitkomplexität, wenn wir die 19 suchen. In diesem Fall müssen wir nämlich genau 10 Vergleiche durchführen. Also genau die Hälfte der vorhandenen Elemente durchlaufen.

Die schlechteste Performance weist unser Algorithmus auf, wenn wir ein Element suchen, das sich nicht im Array befindet. Dann muss nämlich die maximal mögliche Anzahl von 20 Vergleichen durchgeführt werden.

Auch wenn ich Anhänger einer optimistischen Lebensweise bin, müssen wir uns mit dem schlimmsten, den sogenannten worst case Szenario beschäftigen.

Denn genau das sind die Fälle, die den Server lahmlegen, den Anwender beim Support anrufen lassen und den Kunden zur Konkurrenz treiben.

Diese Vereinfachungen ermöglichen uns die Performance unseres Codes mit Hilfe der groß O Notation quantitativ zu bestimmen.

Dröseln wir das ganze mal anhand von einigen Beispielen auf.

Die wichtigsten Klassen der groß O Notation

Beginnen wir mit einem einfachen Beispiel!

Probleme konstanter Komplexität

public static int getZahl(int i){
	 int[] elemente = {4,6,8,2,5,10,11,14,13,19,15,3,34,23,9,7,47,39,21,99};
	 return elemente[i];
}

Diese Methode macht nichts weiter als den Wert an der Array-Postion i zurück zuliefern.

Wie sieht es mit der Zeitkomplexität aus?

Um das Element an Position i zu erhalten benötigen wir genau einen Zugriff.

Was passiert, wenn wir unsere Arraygröße von 20 auf 30 Elemente erweitern?

Genau nix! Wir benötigen immer noch genau einen Zugriff auf das Element i.

Die Zeitkomplexität hängt also nicht von der Menge der betrachteten Daten ab. Deshalb sprechen wir in diesem Fall auch von einem Problem von konstanter Zeitkomplexität.

In der groß O Notation bezeichnen wir konstante Zeitkomplexität mit O(1).

Jetzt noch eine Quizfrage? Was ist die Komplexität des folgenden Codes?

System.out.println(getZahl(10));
System.out.println(getZahl(14));

Hier rufen wir unsere Methode zwei Mal hintereinander auf.

Was ist hier das Ergebnis der groß O Notation? Vielleicht O(2)?

Jepp! Allerdings ist O(1) = O(2) = O(2378754375). Das kannst du mir im Moment einfach glauben. Verstehen wirst du das in Kürze.

Bei Programmen von konstanter Zeitkomplexität ändert sich die Laufzeit des Programms bei zu nehmender Datenmenge also nicht.

Ein Programm, das bei einer Datenmengen von N=1 eine Laufzeit von einer Sekunde aufweist, benötigt auch bei einer Datenmenge von N = 10000 nur eine Sekunde.

Leider ist konstante Zeitkomplexität die Ausnahme.

Wenden wir uns der nächsten Komplexitätklasse zu!

Probleme mit linearer Komplexität

Das kennen wir schon!

Wir hatten in der Methode oben, in der wir in einem 20 elementigen Array nach einem bestimmten Wert gesucht haben festgestellt, dass wir im schlechtesten Fall 20 Vergleiche durchführen müssen.

Wie ändert sich die Situation, wenn wir das Array von 20 auf 30 Elemente erweitern?

Ganz genau! In diesem Fall benötigen wir im schlechtesten Fall 30 Vergleiche.

Die Komplexität unseres Problems wächst also linear mit der Datenmenge, weshalb wir von einem Problem mit linearer Komplexität sprechen.

Benötigt ein Programm von linearer Komplexität im schlechtesten für eine bestimmte Datenmenge 10 Sekunden, dann werden im worst case Szenario für die doppelte Datenmenge 20 Sekunden benötigt.

Mit Hilfe der groß O Notation ausgedrückt schreiben wir O(N).

Und wieder die selbe Quizfrage. Wie ändert sich die groß O Notation, wenn wir die Methode zweimal aufrufen?

Richtig!!! Es ist O(2N) und das ist das selbe wie O(N) oder O(10N).

Auf zur nächsten Komplexitätsklasse!

Probleme von quadratischer Komplexität!

Was ist die Komplexität folgenden Code-Schnipsel?

public static int quadratKomplex(int n){
1:	 int sum = 0;
2:	 for(int i = 1; i<=n; i++){
3:		 for(int j = 1;j<=n;j++){
4:			 sum += i*j;
5:		 }
6:	 }
7:	 return sum;
 }

Was passiert hier?

Die Methode enthält zwei ineinander verschachtelte for Schleifen, die beide von 1 bis zum Parameter n laufen.

Mit jedem Durchlauf der Schleife in Zeile zwei, wird die Anweisung sum += i*j n-mal in der inneren Schleife ausgeführt.

Insgesamt wird die Anweisung aus Zeile 4 also n*n = n² mal ausgeführt und das Ergebnis der Methode ist die Summe aus den Produkten 1*1, 1*2…1*n,2*1,2*2..2*n,..n*n.

Diesen Aufwand nennt man quadratische Komplexität!

Und auch hier gilt wieder, wenn wir die Methode zweimal ausführen, so ist O(N²) = O(2*N²) = O(123*N²).

Wie verändert sich sich die Laufzeit bei Erhöhung von n?

Quadratische Komplexität führt bei Verdopplung der Daten zu einer Vervierfachung, bei einer Verdreifachung zu einer Verneunfachung und bei einer Vervierfachung zu einer um den Faktor 16 größeren Laufzeit.

Wir können also festhalten, dass quadratische Komplexität unsere Ressourcen rasant zur Erschöpfung bringt.

Probleme von der Komplexität N*M

Sonderfall der quadratischen Komplexität ist die N*M Komplexität.

Ein Beispiel dieser Klasse erhalten wir durch eine einfache Modifikation der quadratKomplex Methode von oben.

public static int nmKomplex(int n,int m){
	 int sum = 0;
	 for(int i = 1; i<n; i++){
		 for(int j = 1;j<m;j++){
			 sum += i*j;
		 }
	 }
	 return sum;
 }

In dieser Version haben die ineinander verschachtelten Schleifen unterschiedliche Endindizes.

Die Anweisung sum += i*j wird n*m mal ausgeführt. Setzen wir n=m, so erhalten wir quadratische Komplexität.

Eine Verdopplung der Laufzeit entsteht, wenn wir entweder n oder m verdoppeln.

Ausgedrückt durch die O Notation schreiben wir O(N*M).

Probleme von logarithmischer Komplexität

Wenden wir uns der nächsten Komplexitätsklasse zu. Beginnen wir erneut mit einem Beispiel.

1: public static void logKomplex(int n){
2:     for(int i = 1;i<=n;i=i*2){
3:	System.out.println("Schleifenzähler: "+i);	
4:    }
5: }

Was ist die Komplexität dieser Methode?

Das besondere ist hier, dass wir in jedem Schleifendurchlauf die Zählervariable verdoppeln.

Überlegen wir uns wie oft die Programmausgabe in Zeile drei für n=10 erfolgt.

Hierfür müssen wir zunächst feststellen, wie viele Schleifendurchläufe stattfinden bis die Zählervariable i einen Wert größer oder gleich n annimmt.

Im ersten Schleifendurchlauf ist i=1, im zweiten i=2, im dritten i=4 und im vierten Durchlauf gilt i=8. Der fünfte Schleifendurchlauf wird nicht durchgeführt, da dann i=16 also i>ngilt.

Für n=10 finden also genau vier Schleifendurchläufe statt.

Wie können wir die Anzahl der Schleifendurchläufe formelmäßig angeben?

Schreiben wir die Werte der Zählervariable in einer etwas anderen Form.

Es ist i=1=2⁰, i=2=2¹, i=4=2², i=8=2³ und i=16=2⁴.

Und genau diese Beobachtung können wir ausnutzen. Denn der Exponent zur Basis 2 können wir mir Hilfe des Logarithmus zur Basis zwei berechnen. So ist z.B. log(16) = 4 (Basis 2!).

In unserem Beispiel terminiert die for Schleife sobald 2^k &gt n für ein k gilt wobei k für die Anzahl der Schleifen-Durchläufe steht.

Nach unseren Vorüberlegungen gilt für die Anzahl der Schleifendurchläufe also k = log(n).

Hierbei haben wir allerdings eines zu beachten!

Die Anzahl der Schleifendurchläufe kann nur Ganzzahlig sein! Der Wertebereich des Logarithmus ist aber auf den reellen Zahlen definiert, daher ist das Ergebnis unserer Formel immer auf die nächste ganze Zahl aufzurunden.

Überprüfen wir die Formel für n=10. Wir hatten bereits festgestellt, dass in diesem Fall vier Schleifendurchläufe stattfinden.

Und tatsächlich gilt log(10) = 3,321 was nach Aufrundung genau 4 ergibt.

Die Anzahl der Schleifendurchläufe nimmt also mit der Erhöhung von n logarithmisch zu. In der O Notation ausgedrückt schreiben wir O(log(n)) und sprechen von logarithmischer Komplexität.

Interessant an dieser Klasse ist, dass die Logarithmusfunktion für große Werte nur noch geringfügig ansteigt und sich daher die Performance für große n und sehr große n nur noch geringfügig unterscheidet.

Die Rechenregeln der O Notation

Die O Notation ist also ein Größenmaß, an dem sich ablesen lässt wie sich die Performance bei zu nehmender Verarbeitungsmenge verändert.

Da bei kleinen Datenmengen die Performance-Frage uninteressant ist, nehmen wir die Verarbeitungsmenge N als sehr groß an.

In der Theorie gibt es keine Einschränkung, weshalb wir einen mathematischen Grenzprozess durchführen und N gegen unendlich gehen lassen.

Und hiermit lassen sich auch die von uns in den Beispielen gemachten Vereinfachungen erklären weshalb z.B. O(2N) = O(N) gilt.

Die Grenzwerte der Ausdrücke  N, 2N, 56N..424N sind, wenn wir N gegen unendlich streben lassen alle gleich und zwar unendlich. Aus diesem Grund sind Konstanten bei der O Notation vernachlässigbar.

In der Praxis hat das den großen Vorteil, dass wir eine Funktion, deren Komplexität wir kennen, mehrfach aufrufen können ohne die O Notation zu verändern.

Aus der Tatsache, dass wir eine Grenzwertbetrachtung machen ergibt sich eine weitere wichtige Konsequenz.

Schauen wir uns mal folgenden Codeschnipsel an:

Was ist die Komplexität dieses Codes?

1: public static void asympDemo(int n){
2:	int sum = 0;
3:	for(int i = 1;i<=n;i++){
4:	   for(int j = 1;j<=n;j++){
5:		sum += i*j;
6:	    }
7:	}
8:	for(int i = 1;i<=n;i++){
9:		sum += i;
10:	}
11:}

In den Zeilen drei bis sieben wird die Anweisung sum += i*j; innerhalb zweier ineinander verschachtelter for-Schleifen, die jeweils von 1 bis n laufen N&sup2 mal ausgeführt.

Zum Abschluss (Zeile 8-10) wird noch die Anweisung sum += 1 n-mal ausgeführt

Insgesamt finden also N²+N Operationen statt.

Und da wir bei der O Notation eine Grenzwertbetrachtung machen, ist nur der Term mit der höchsten Potenz ausschlaggebend.

In unserem Fall können wir den linearen Term also vernachlässigen und wir erhalten O(N²).

Unsere Methode ist somit von quadratischer Komplexität.

Insgesamt können wir also zwei Rechenregeln für die O Notation festhalten:

1. Konstanten können vernachlässigt werden. Es gilt O(cN) = O(N) und O(N+C) = O(N).
2. Nur die jeweils größte Potenz einer Verabeitungsmenge spielt eine Rolle. Es ist O(N^m+N^k) = O(N^m), falls m>k.

Fazit: Die O Notation ist ein Werkzeug um die Performance von Programmen unabhängig von der zugrundeliegenden Hardware zu bewerten wodurch ein objektiver Vergleich von verschiedenen Algorithmen möglich wird. Zu beachten ist hier allerdings das die O Notation eine Worst-Case Betrachtung darstellt und daher die durchschnittliche Laufzeit eines Algorithmus in der Praxis deutlich besser sein kann.

Hast du Fragen? Dann ab damit in die Kommentare!

Hat dir der Artikel gefallen? Dann folge uns doch am besten gleich auf Facebook!