The Big O Notation

Die Big-O-Notation wird verwendet, um die Rechenkomplexität eines Programms oder einer Datenstruktur anzugeben. Das bedeutet im Grunde: Wie viele Schritte werden benötigt, um eine bestimmte Aktion auszuführen.

The Big ?

Big O notation is the language we use for talking about the efficiency of data structures and algorithms.

The Big O Notation

---

Die Big O Notation ist eine mathematische Notation (ein beschreibender Ausdruck - Darstellung von Rechenoperationen, Bewegungsverläufen und Reihenfolgen anhand von Formeln), welche das Limit einer Funktion beschreibt, wenn das Argument/der Fall zu einem bestimmten Wert oder Undendlichkeit tendiert. Bestimmte Operationen können mehr oder weniger gut performen, abhängig von ihrer Datenstruktur/ ihrem Algorithmus. The Big O hilft uns dabei die Performance eines Algorythmus zu beschreiben und zu bestimmen, ob er skalierbar ist oder nicht.

Die Big O Notation wird von Entwicklern verwendet, um zu kommunizieren, wie gut ihr Programm mit einer Zunahme der Eingaben umgeht (wichtig bei großen Datenmengen). Sie kann ein Maß dafür sein, wie schnell ein Programm läuft ("Runtime-Complexity") oder wie viel Speicherplatz(Memory) es verbraucht ("Space-Complexity").

Kurz gesagt: Wenn ein Programm in der Lage ist, eine immer größere Menge an Eingaben in der gleichen Zeit wie eine kleine Menge an Eingaben zu verarbeiten, wird es gemäß der Big O Notation gut abschneiden.

Mit der Big O Notation können wir die Komplexität unseres Codes ausdrücken. Meist geht es um einen Kompromiss zwischen Speicher und Zeit.

• O(1): Constant Time Complexity
  Der Algorithmus wird gleich ausgeführt, unabhängig davon, wie viele Elemente sich in der Liste befinden. Zum Beispiel: Find element in an array by its index.
• O(log n): Logarithmic Time Complexity
  Die Zeit, die der Algorithmus benötigt, um zu laufen, wird gleich bleiben, egal wie viele Elemente sich in der Liste befinden. Ein Algorithmus mit logarithmic time complexity ist skalierbarer als einer mit linear time complexity. Zum Beispiel: BinarySearch in sorted array.
• O(n): Linear Time Complexity
  Je mehr Elemente in der Liste enthalten sind, desto länger dauert es, bis der Algorithmus ausgeführt wird. Die Inputgröße ist also entscheidend. Zum Beispiel: Looping through an array.
• O(n*log n): Log Linear Time Complexity
• O(n^2): Quadratic Time Complexity
  Wenn die Elemente in der Liste zunehmen, erhöht sich die Zeit, die der Algorithmus benötigt, um exponentiell zu laufen.
  Zum Beispiel: A loop within a loop.
• O(n^3): Cubic Time Complexity
• O(2^n): Exponential Time Complexity
  Zum Beispiel: Looping over every possible combination in an array.
• O(n!): Factorial Time Complexity

Goldene Regel: Mehrere Ausdrücke immer auf einen Ausdruck (worst-case) herunterbrechen.

Space-Complexity

Die Komplexität steigt, wenn...
- Variablen zugewiesen werden
- neue Datenstrukturen kreiert werden
- Funktionen aufgerufen und zugewiesen werden

O(1) space
z.B.
public void greet (String[ ] names){
for (int i= 0; i< names.length; i++)
sout("hi"+ names[i]);
}

O (n) space
z.B.
public void greet (String[ ] names){
String[ ] copy = new String [names.length];
for (int i = 0; i< names.length; i++)
sout("hi"+ names[i]);
}

Je mehr Items im Array sind, desto mehr Space wird benötigt. Wir betrachten nur den zusätzlichen Space, den wir zuweisen müssen, relativ gesehen zur Inputgröße.