Werkblad Algoritmen & complexiteit met antwoorden

Een O(n²)-algoritme doet 1 seconde over n = 1000. Hoe lang doet het ongeveer over n = 2000?

1. A2 seconden
2. B4 seconden
3. C8 seconden
4. D1 seconde

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

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

Wat is de tijdcomplexiteit van binair zoeken in een gesorteerde array?

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

De recurrente betrekking T(n) = 2T(n/2) + O(n) heeft als oplossing:

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

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

1. AHelemaal geen deelproblemen, dus het kan in één stap worden opgelost
2. BEén enkele lus
3. COverlappende deelproblemen en optimale substructuur
4. DAlleen willekeurige invoer

Wat is de tijdcomplexiteit van: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Als je beide eindpunten van elke kant in een maximale koppeling neemt, krijg je een knoopoverdekking. Hoe goed is deze overdekking?

1. AHoogstens twee keer zo groot als een minimale knoopoverdekking
2. BHoogstens log n keer het minimum
3. CAltijd een minimale knoopoverdekking
4. DVan onbekende kwaliteit vergeleken met het optimum

Hoe wordt het handelsreizigersprobleem geclassificeerd?

1. ADe beslissingsversie is NP-volledig en de optimalisatieversie is NP-moeilijk
2. BHet is onbeslisbaar
3. CDe beslissingsversie zit in P, maar de optimalisatieversie is NP-volledig
4. DHet zit in P, omdat het algoritme van Dijkstra het oplost door elke stad één keer te bezoeken