Algoritmen & complexiteit: oefenvragen met uitleg

1Wat complexiteit meet

Een algoritme is een eindige lijst van precieze stappen die een probleem oplost, zoals een lijst sorteren of een naam in een telefoonboek zoeken.

Twee algoritmen kunnen hetzelfde probleem oplossen maar heel verschillend veel tijd kosten. Complexiteit beschrijft hoe het werk groeit als de invoer groter wordt.

De grootte van de invoer heet n: het aantal items om te sorteren, de lengte van een lijst, het aantal knopen in een graaf.

Denk aan het zoeken van een naam in een telefoonboek van 1000 pagina’s. Elke pagina lezen kost maximaal 1000 stappen. Het boek in het midden openen en telkens halveren kost ongeveer 10 stappen.

Tijdcomplexiteit telt de stappen. Ruimtecomplexiteit telt het extra geheugen. Beide worden geschreven als functie van n.

Meestal kijk je naar het slechtste geval: het meeste werk over alle invoeren van grootte n. Soms wordt in plaats daarvan naar het gemiddelde of het beste geval gevraagd.

2Big O en de groeiklassen

De Big O-notatie houdt alleen over wat telt voor grote n. Je laat constante factoren weg en houdt alleen de snelst groeiende term.

Voor n = 1000 is de n²-term 3 000 000, terwijl 5n maar 5000 is. De kleinere termen veranderen het totaal nauwelijks.

Deze klassen komen steeds terug, van langzaamste naar snelste groei:

• O(1), constant: een array-element lezen via zijn index.
• O(log n), logaritmisch: binair zoeken, dat het probleem in elke stap halveert.
• O(n), lineair: één keer langs alle items, zoals het zoeken van de grootste waarde.
• O(n log n): goede sorteeralgoritmen zoals merge sort.
• O(n²), kwadratisch: twee geneste lussen over de items, zoals bubble sort.
• O(2ⁿ), exponentieel: elke deelverzameling proberen. Het wordt snel onbruikbaar.

Big O is een bovengrens: het werk groeit hoogstens zo snel. Ω (Big Omega) is een ondergrens en Θ (Theta) is een scherpe grens, zowel boven als onder.

Het grondtal van een logaritme doet er in Big O niet toe, omdat logaritmen met verschillende grondtallen alleen door een constante factor verschillen.

3Zoeken, sorteren en recursie

Een paar algoritmen komen in bijna elke cursus voor. Leer hun complexiteiten als feiten.

• Lineair zoeken controleert items één voor één: O(n). Binair zoeken heeft een gesorteerde array nodig en halveert het bereik in elke stap: O(log n).
• Bubble sort, insertion sort en selection sort vergelijken en verwisselen items in geneste lussen: O(n²). Insertion sort is O(n) op een array die al gesorteerd is.
• Merge sort splitst de array in helften, sorteert ze en voegt ze samen: O(n log n) in elk geval, met O(n) extra geheugen.
• Quicksort splitst rond een pivot: O(n log n) gemiddeld, maar O(n²) in het slechtste geval, bijvoorbeeld een gesorteerde array met het eerste element als pivot.
• Geen sortering die alleen items vergelijkt, kan in het slechtste geval beter zijn dan Ω(n log n). Counting sort is sneller omdat het niet vergelijkt.

Een recursieve functie roept zichzelf aan op een kleinere invoer totdat hij een basisgeval bereikt dat hij direct beantwoordt. Zijn rekentijd wordt geschreven als een recurrente betrekking:

• T(n) = T(n/2) + O(1) geeft O(log n), zoals binair zoeken.
• T(n) = 2T(n/2) + O(n) geeft O(n log n), zoals merge sort.
• T(n) = T(n − 1) + O(n) geeft O(n²).
• T(n) = 2T(n − 1) + O(1) geeft O(2ⁿ).

Drie ontwerpideeën zijn het kennen waard. Verdeel en heers splitst, lost op en combineert. Greedy kiest in elke stap de lokaal beste keuze. Dynamisch programmeren slaat de antwoorden op van overlappende deelproblemen, zodat ze maar één keer worden berekend.

4De methode stap voor stap

Zo vind je de tijdcomplexiteit van een stuk code:

1. Bepaal wat n is: de grootte van de invoer.
2. Tel hoe vaak elke lus draait. Een lus die elke keer 1 optelt, draait ongeveer n keer. Een lus die verdubbelt of halveert, draait ongeveer log₂ n keer.
3. Lussen binnen elkaar vermenigvuldig je. Lussen na elkaar tel je op.
4. Schrijf bij een recursieve functie de recurrente betrekking op: hoeveel aanroepen, op welke grootte, plus het werk per aanroep.
5. Houd de snelst groeiende term en laat de constanten weg.
6. Controleer met een klein getal, bijvoorbeeld n = 8 of n = 1024.

Noem bij een theorievraag eerst het algoritme of idee dat wordt beschreven, en haal dan zijn complexiteit en voorwaarden op (gesorteerde invoer, niet-negatieve gewichten, overlappende deelproblemen).

5Een uitgewerkt voorbeeld

Volg elke stap. Probeer de volgende stap te voorspellen voordat je hem opent.

6Veelgemaakte fouten

• Lussen vermenigvuldigen die na elkaar draaien. n + n = 2n is nog steeds O(n).
• Constanten houden, zoals in O(2n) of O(n/2). Beide zijn O(n).
• Een verdubbelingslus tellen als n rondes. Hij draait ongeveer log₂ n keer.
• Binair zoeken gebruiken op ongesorteerde gegevens, of op een gelinkte lijst waar het midden niet in één stap bereikt kan worden.
• Het gemiddelde geval van quicksort geven terwijl naar het slechtste geval wordt gevraagd.
• Denken dat grote O “precies” betekent. O(n²) is een bovengrens; Θ(n²) is de exacte groei.

7Hoe tentamenvragen eruitzien

• Makkelijk: kernbegrippen en feiten. De complexiteit van binair zoeken, merge sort of toegang tot een array, de betekenis van O, Ω en Θ, wat recursie is.
• Gemiddeld: concepten toepassen. De complexiteit van een stuk code, een recurrente betrekking oplossen, hoe de tijd verandert als n verdubbelt, welk algoritme bij een taak past.
• Moeilijk: gevallen en analyse. De hoofdstelling (master theorem), slechtste gevallen van quicksort, greedy versus dynamisch programmeren, en de klassen P, NP en NP-volledig.

P bevat de problemen die in polynomiale tijd op te lossen zijn. NP bevat de problemen waarvan de oplossingen in polynomiale tijd gecontroleerd kunnen worden. Elk probleem in P zit in NP; of P = NP is nog onbekend.