Werkblad Algoritmen & complexiteit met antwoorden

Wat is log₂ 1024?

1. A10
2. B32
3. C12
4. D512

Wat is de best-case tijdcomplexiteit van insertion sort op een al gesorteerde array?

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

Wat betekent f(n) = Θ(g(n))?

1. Af groeit strikt langzamer dan g
2. Bf is voor elke n altijd kleiner dan g, dus g begrenst f van boven maar nooit van onderen
3. Cf groeit even snel als g, van boven en van onderen begrensd door constante veelvouden van g
4. Df groeit strikt sneller dan g

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

1. AMergesort heeft geen recursieve structuur
2. BMergesort is al O(n)
3. CDe deelproblemen overlappen niet, dus er valt niets te hergebruiken
4. DDynamisch programmeren werkt alleen op grafenproblemen, niet op arrays

Wat betekent het dat een probleem een optimale deelstructuur heeft?

1. AElk deelprobleem heeft dezelfde grootte
2. BHet probleem heeft precies één optimale oplossing, die alle deelproblemen delen
3. CEen optimale oplossing kan worden opgebouwd uit optimale oplossingen van de deelproblemen
4. DHet probleem kan in constante tijd worden opgelost

Waarom schakelen veel sorteerroutines in bibliotheken over op insertion sort voor heel kleine deelarrays?

1. AInsertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
2. BInsertion sort is in het slechtste geval O(n log n)
3. CRecursieve algoritmen kunnen geen arrays van minder dan 10 elementen aan
4. DInsertion sort gebruikt voor grote invoer minder geheugen dan elk ander sorteeralgoritme

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

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

Wat is de tijdcomplexiteit van het opbouwen van een binaire heap uit n ongesorteerde elementen met de bottom-upmethode?

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