Was ist die O-Notation (Big O-Notation)?

O-Notation (Big O-Notation) ist eine Methode zur Beschreibung der asymptotischen Bewertung der Komplexität eines Algorithmus, also wie die Laufzeit oder der Speicherverbrauch mit zunehmender Eingabedatenmenge wächst.

Zum Beispiel bedeutet eine Komplexität von O(n), dass die Laufzeit linear mit der Eingabemenge wächst. Bei O(n²) wächst die Laufzeit proportional zum Quadrat der Eingabemenge.

Beispiel in Go:

func sum(arr []int) int {
    total := 0
    for _, v := range arr {
        total += v
    }
    return total
}

Die Funktion sum hat eine Komplexität von O(n), da sie alle Elemente des Arrays einmal durchläuft.