Complexiteit en Big-O: zo schat je de looptijd van een algoritme

Twee programma's kunnen precies hetzelfde antwoord geven en toch totaal verschillend presteren. Het ene sorteert een miljoen getallen in een fractie van een seconde, het andere is na een uur nog bezig. Complexiteit (complexity) is de taal waarmee je dat verschil beschrijft zonder een stopwatch: je telt hoe het aantal stappen groeit als de invoer groter wordt.

Je hebt dit nodig op elk tentamen algoritmen, in vrijwel elk technisch sollicitatiegesprek ("wat is de complexiteit van jouw oplossing?") en in de praktijk, zodra je data groter wordt dan je testset. Alle andere onderwerpen hier, van sorteren tot grafen, gebruiken deze notatie.

Big-O en Θ: het idee

Noem de grootte van de invoer n (het aantal elementen in een lijst, het aantal knopen in een graaf). De looptijd T(n) is het aantal basisstappen: een vergelijking, een toekenning, een optelling.

• Big-O (O) is een bovengrens: T(n) = O(f(n)) betekent dat T(n) voor grote n hooguit een constante keer f(n) is.
• Theta (Θ) is een strakke grens: T(n) groeit precies zo snel als f(n), op een constante factor na. Zowel boven- als ondergrens.

Strikt genomen is een enkele lus ook O(n²), want n² is óók een bovengrens. Maar dat is een nutteloos antwoord. Op Practicely en op de meeste tentamens bedoelen we met Big-O de strakke grens: een enkele lus is O(n), punt.

Rekenregels

Je hoeft nooit precies te tellen. Twee regels doen het meeste werk:

1. Constanten vallen weg. 3n + 7 is O(n). n/2 is ook O(n).
2. Alleen de dominante term telt. n² + 100n + 5000 is O(n²), want voor grote n maakt de rest niets meer uit.

Zie het zo: bij n = 1000 is n² een miljoen en 100n maar honderdduizend. Bij n = 1.000.000 is het verschil een factor tienduizend.

Verder geldt: het grondtal van een logaritme maakt in Big-O niet uit, omdat log₁₀ n en log₂ n een constante factor van elkaar verschillen. Staat er log n, dan bedoelen we log₂ n.

De veelvoorkomende klassen

Van snel naar traag:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Het verschil tussen O(n log n) en O(n²) is bij duizend elementen al een factor honderd. Daarom loont het om de klasse van je algoritme te kennen.

Lussen tellen

Het meeste werk bij het bepalen van de complexiteit is: kijk hoe vaak de binnenste opdracht wordt uitgevoerd.

Enkele lus

for i in range(n):
    totaal += a[i]

for (int i = 0; i < n; i++) {
    totaal += a[i];
}

De body draait n keer: O(n).

Geneste lussen

for i in range(n):
    for j in range(i + 1, n):
        if a[i] == a[j]:
            gevonden = True

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (a[i] == a[j]) {
            gevonden = true;
        }
    }
}

Voor i = 0 draait de binnenste lus n-1 keer, voor i = 1 n-2 keer, enzovoort tot 0. Samen:

(n-1) + (n-2) + … + 1 + 0 = n(n-1)/2

Bij n = 16 zijn dat 120 vergelijkingen, bij n = 1000 precies 499.500. Constante (½) weg, dominante term (n²) houden: O(n²). Dat de binnenste lus "maar half zo lang" is, verandert de klasse niet.

Gehalveerde of verdubbelde teller

i = n
while i > 0:
    i //= 2        # i wordt telkens gehalveerd

int i = n;
while (i > 0) {
    i /= 2;        // i wordt telkens gehalveerd (integerdeling)
}

Bij n = 16 neemt i de waarden 16, 8, 4, 2, 1 aan: 5 iteraties. Elke stap halveert het werk, dus het aantal stappen is ongeveer log₂ n: O(log n).

Hetzelfde geldt voor een teller die verdubbelt:

i = 1
while i < n:
    i *= 2         # 1, 2, 4, 8, ... tot n

int i = 1;
while (i < n) {
    i *= 2;        // 1, 2, 4, 8, ... tot n
}

Let op het verschil met i -= 2 of i += 2: dat zijn n/2 stappen, dus gewoon O(n).

Sequentiële stukken

Twee stukken code ná elkaar tel je op, en dan houd je de grootste:

for i in range(n):          # O(n)
    totaal += a[i]
for i in range(n):          # O(n²)
    for j in range(n):
        paren += 1

for (int i = 0; i < n; i++) {          // O(n)
    totaal += a[i];
}
for (int i = 0; i < n; i++) {          // O(n²)
    for (int j = 0; j < n; j++) {
        paren++;
    }
}

O(n) + O(n²) = O(n²). Nesten vermenigvuldigt, achter elkaar zetten telt op.

Een lus met een logaritmische binnenlus

for i in range(n):
    j = 1
    while j < n:
        j *= 2

for (int i = 0; i < n; i++) {
    int j = 1;
    while (j < n) {
        j *= 2;
    }
}

De buitenste lus draait n keer, de binnenste elke keer log n keer: O(n log n).

Recursie en recurrente betrekkingen

Bij een recursieve functie schrijf je de looptijd op als een recurrente betrekking (recurrence relation): een formule die T(n) uitdrukt in T van een kleinere invoer.

Een paar standaardgevallen:

Een voorbeeld: de som van een lijst, recursief.

def som(a, n):
    # basisgeval: een lege lijst heeft som 0
    if n == 0:
        return 0
    # één recursieve aanroep op n-1, plus constant werk
    return som(a, n - 1) + a[n - 1]

print(som([4, 1, 7, 3], 4))  # 15

static int som(int[] a, int n) {
    // basisgeval: een lege lijst heeft som 0
    if (n == 0) {
        return 0;
    }
    // één recursieve aanroep op n-1, plus constant werk
    return som(a, n - 1) + a[n - 1];
}

Dit is T(n) = T(n-1) + 1. Uitschrijven ("ontrollen") laat zien wat er gebeurt: T(n) = T(n-2) + 2 = T(n-3) + 3 = … = T(0) + n, dus O(n).

De mastermethode

Voor recursies die het probleem in gelijke stukken delen, is er een kant-en-klaar recept: de mastermethode (master theorem). Hij werkt voor betrekkingen van de vorm

T(n) = a · T(n/b) + n^d

met a ≥ 1 deelproblemen, elk van grootte n/b, en n^d werk buiten de recursie (splitsen en samenvoegen). Je vergelijkt a met b^d:

Uitgewerkt:

Let op het tweede voorbeeld: constant werk is n⁰, dus d = 0 en b^d = 1.

De intuïtie: teken de recursieboom. In geval 1 doet de wortel het meeste werk, in geval 3 zitten de kosten in de enorme hoeveelheid bladeren, en in geval 2 kost elk van de log n niveaus evenveel.

De mastermethode werkt niet voor T(n) = T(n-1) + n: daar wordt n niet gedeeld maar met één verminderd. Die los je op door te ontrollen, zoals hierboven.

Complexiteit in één tabel

Veelgemaakte fouten op het tentamen

1. Elke geneste lus is O(n²) noemen. Kijk naar wat de binnenste lus doet. Halveert de teller, dan is het O(n log n). Loopt de binnenste lus een vast aantal keer (bijvoorbeeld 3), dan is het gewoon O(n).
2. Optellen en vermenigvuldigen door elkaar halen. Lussen ná elkaar: optellen, de grootste houden. Lussen ín elkaar: vermenigvuldigen.
3. Een te ruime grens geven. O(n²) voor een enkele lus is technisch niet fout, maar levert op het tentamen geen punten op. Geef de strakke grens.
4. d verkeerd aflezen bij de mastermethode. Constant werk betekent d = 0, niet d = 1. En vergelijk a met b^d, niet met b.
5. De mastermethode toepassen op T(n-1). Alleen bij delen door b werkt het recept; bij aftrekken ontrol je de recursie.

Samenvatting

• Big-O beschrijft hoe de looptijd groeit met n; constanten en lagere termen vallen weg.
• Op het tentamen geef je de strakke grens: een enkele lus is O(n), niet O(n²).
• Geneste lussen vermenigvuldig je, opeenvolgende lussen tel je op; een halverende teller geeft log n.
• Recursie schrijf je als recurrente betrekking; bij T(n) = aT(n/b) + n^d vergelijk je a met b^d.
• Volgorde om te onthouden: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).