Big O Notation für Anfänger – Einfach erklärt

Wenn du in der Welt der Programmierung unterwegs bist, hast du wahrscheinlich schon von Big O Notation gehört. Aber was genau ist das? In diesem Artikel werde ich dir eine einfache Einführung in Big O Notation geben.

Was ist Big O Notation?

Big O Notation ist eine Methode, um die Laufzeit von Algorithmen zu beschreiben. Genauer gesagt, beschreibt Big O Notation, wie schnell die Laufzeit eines Algorithmus mit der Größe des Inputs wächst. Es ist ein Maß dafür, wie effizient ein Algorithmus ist.

Ein Beispiel: Ein Algorithmus, der eine Liste von Zahlen ausgibt, hat eine Laufzeit von O(n) (ausgeprochen „O von n“). Das bedeutet, dass die Laufzeit des Algorithmus genau mit der Größe der Liste mitwächst. n steht hier also für die Anzahl der Elemente in der Liste.

Wofür wird Big O Notation verwendet?

Big O Notation ist eine wichtige Konzeption in der Informatik, da es Programmierern hilft, effiziente Algorithmen zu schreiben. Es ist auch nützlich, um zu verstehen, warum einige Algorithmen schneller sind als andere.

Wie funktioniert Big O Notation?

Big O Notation gibt an, wie schnell die Laufzeit eines Algorithmus wächst, wenn die Größe des Inputs wächst. Es verwendet eine mathematische Notation, um diese Wachstumsrate zu beschreiben.

In der Regel werden die folgenden Symbole verwendet, um die Wachstumsrate zu beschreiben (in absteigender Effizienz sortiert):

O(1): Konstante Laufzeit

O(log n): Logarithmische Laufzeit

O(n): Lineare Laufzeit

O(n log n): N log N Laufzeit

O(n²): Quadratische Laufzeit

O(2^n): Exponentielle Laufzeit

Es gibt noch viele weitere Symbole, aber diese sind die häufigsten.

Am Beispiel erklärt

Schau dir den folgenden JavaScript Code (das Beispiel funktioniert für alle Programmiersprachen) an:

let myArray = [1, 2, 3, 4, 5];
  
for (let i = 0; i < myArray.length; i++) {
    console.log(myArray[i]);
}

Wenn du eine Schleife hast, die alle Elemente eines Arrays ausgibt, hast du eine Laufzeit von O(n), wobei n die Größe des Arrays ist. Das liegt daran, dass die Schleife einmal durch das gesamte Array iteriert, um jedes Element auszugeben. Da die Anzahl der Iterationen proportional zur Größe des Arrays ist, wird die Laufzeit als O(n) bezeichnet.

Wenn du noch mehr zum Thema Big O Notation erfahren möchtest, dann schau mal hier.