Werkblad Algoritmen & complexiteit met antwoorden

Welke hiervan groeit het langzaamst als n groot wordt?

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

De looptijd van een algoritme is O(n). Hoe heet deze groei?

1. AKwadratisch
2. BConstant
3. CLogaritmisch
4. DLineair

Wat is het basisgeval van een recursieve functie?

1. AHet geval met de grootste invoer, dat vóór alle recursieve aanroepen wordt afgehandeld
2. BEen geval dat direct wordt beantwoord zonder nog een recursieve aanroep
3. CDe eerste regel van de functie
4. DDe aanroep die het meeste geheugen gebruikt

De tijdcomplexiteit van naïef recursief Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

1. AExponentieel
2. BConstant
3. CLogaritmisch
4. DLineair

Waarom wordt het grondtal van een logaritme in grote-O-notatie meestal weggelaten, zoals in O(log n)?

1. AHet grondtal doet er alleen toe voor kleine n
2. BLogaritmen met verschillende grondtallen verschillen alleen een constante factor
3. CLogaritmen worden altijd afgerond op gehele getallen
4. DAlle logaritmen in de informatica hebben grondtal 10, dus het is impliciet

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

1. AOverlappende deelproblemen en optimale substructuur
2. BHelemaal geen deelproblemen, dus het kan in één stap worden opgelost
3. CAlleen willekeurige invoer
4. DEén enkele lus

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

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

Een probleem is NP-volledig als het:

1. AOnmogelijk op te lossen is
2. BIn polynomiale tijd oplosbaar is
3. CBuiten NP valt maar moeilijker is dan alle NP-problemen, zoals het stopprobleem
4. DIn NP zit en elk NP-probleem er in polynomiale tijd naar te reduceren is