Werkblad Algoritmen & complexiteit met antwoorden

Wat betekent het als een bewerking in O(1) tijd loopt?

1. ADe looptijd groeit niet met de invoergrootte
2. BHet kan maar één keer worden uitgevoerd
3. CHet duurt altijd precies één seconde
4. DHet verwerkt precies één element per seconde looptijd

Een algoritme met twee geneste lussen die elk n keer worden doorlopen, heeft doorgaans welke complexiteit?

1. AO(n)
2. BO(log n)
3. CO(2n)
4. DO(n²)

Hoe werkt selection sort?

1. AHet zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren
2. BHet splitst de array in helften en voegt die samen
3. CHet voegt elk element door verschuiven in een groeiend gesorteerd deel in
4. DHet verwisselt steeds naast elkaar liggende elementen die in de verkeerde volgorde staan

De ondergrens voor sorteren op basis van vergelijkingen in het slechtste geval is:

1. AΩ(log n)
2. BΩ(n²)
3. CΩ(n log n)
4. DΩ(n)

Je sorteert een array van n elementen één keer en beantwoordt daarna k lidmaatschapsvragen met binair zoeken. Wat zijn de totale kosten?

1. AO(k n log n)
2. BO(nk)
3. CO(n log n + k log n)
4. DO(n + k)

Wat is de worst-case tijdcomplexiteit van quicksort?

1. AO(log n)
2. BO(n²)
3. CO(n)
4. DO(n log n)

Karatsuba-vermenigvuldiging voldoet aan T(n) = 3T(n/2) + O(n). Wat is de oplossing?

1. AΘ(n^{log₂ 3}), ongeveer n^1,585
2. BΘ(n³)
3. CΘ(n log n)
4. DΘ(n²)

Welke uitspraak over het selecteren van het k-de kleinste element van een ongesorteerde array is juist?

1. ASelectie heeft altijd Ω(n log n) nodig, omdat er gesorteerd moet worden
2. BSelectie is alleen mogelijk in O(n²)
3. CQuickselect loopt in het slechtste geval in O(log n), omdat het maar aan één kant van de pivot recursief verdergaat
4. DQuickselect loopt verwacht in O(n), en median-of-medians garandeert O(n) in het slechtste geval