Werkblad Algoritmen & complexiteit met antwoorden

Wat beschrijft de worst-case looptijd van een algoritme?

1. ADe maximale tijd die het nodig heeft over alle invoeren van grootte n
2. BDe tijd die het nodig heeft voor de kleinste invoer
3. CDe tijd die het nodig heeft op een trage computer
4. DDe verwachte tijd die het nodig heeft voor een willekeurige invoer van grootte n

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

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

Een element in een array via de index benaderen kost:

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

Wat is de tijdcomplexiteit van het berekenen van het n-de Fibonaccigetal met een bottom-uptabel?

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

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

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

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)

Insertion sort loopt in O(n) op gesorteerde invoer. Is dit in tegenspraak met de ondergrens Ω(n log n) voor sorteren met vergelijkingen?

1. AJa, maar alleen voor arrays korter dan 100
2. BJa, de ondergrens is dus fout
3. CNee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is
4. DNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer

Hoe wordt het handelsreizigersprobleem geclassificeerd?

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