Werkblad Algoritmen & complexiteit met antwoorden

Welke van deze looptijden is polynomiaal?

1. AO(n³)
2. BO(n!)
3. CO(2ⁿ)
4. DO(nⁿ)

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

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

Wat is de grote O van 3n² + 5n + 2?

1. AO(3n²)
2. BO(5n)
3. CO(n³)
4. DO(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(n + k)
2. BO(k n log n)
3. CO(nk)
4. DO(n log n + k log n)

Wat is de oplossing van de recurrente betrekking T(n) = T(n − 1) + O(1)?

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

Wat is de tijdcomplexiteit van het standaardalgoritme voor dynamisch programmeren voor de langste gemeenschappelijke deelrij van strings met lengte m en n?

1. AO(m + n)
2. BO(2^m+n)
3. CO(mn)
4. DO(mn log n)

Wat zijn de tijd- en ruimtekosten van het berekenen van het n-de Fibonaccigetal met een lus die alleen de laatste twee waarden bewaart?

1. AO(log n) tijd en O(n) ruimte
2. BO(2ⁿ) tijd en O(1) ruimte
3. CO(n) tijd en O(n) ruimte
4. DO(n) tijd en O(1) ruimte

Het algoritme van Strassen vermenigvuldigt matrices met 7 in plaats van 8 recursieve vermenigvuldigingen van blokken van halve grootte. Wat is de looptijd?

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