Werkblad Algoritmen & complexiteit met antwoorden

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

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

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

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

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

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

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

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

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

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 worden altijd afgerond op gehele getallen
3. CLogaritmen met verschillende grondtallen verschillen alleen een constante factor
4. DAlle logaritmen in de informatica hebben grondtal 10, dus het is impliciet

Welke grens is juist voor log(n!)?

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

Welke twee dingen moeten worden aangetoond om te bewijzen dat een beslissingsprobleem X NP-volledig is?

1. AX zit in NP, en een bekend NP-volledig probleem reduceert in polynomiale tijd tot X
2. BX reduceert tot een probleem in P, en X zit in NP
3. CX zit in P, en X reduceert tot SAT
4. DX heeft geen polynomiaal algoritme, en X is beslisbaar