Werkblad Algoritmen & complexiteit met antwoorden

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

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

Welke hiervan groeit het langzaamst als n groot wordt?

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

Wat beschrijft de average-case looptijd?

1. ADe verwachte tijd over een gegeven verdeling van invoeren van grootte n
2. BDe tijd voor een invoer van gemiddelde lengte
3. CDe middelste waarde tussen de looptijden in het beste en het slechtste geval
4. DDe tijd op de meest gebruikte computer

Een gretig (greedy) algoritme:

1. AGeeft altijd de optimale oplossing
2. BGebruikt alleen recursie
3. CProbeert elke mogelijke oplossing
4. DMaakt bij elke stap de lokaal beste keuze

Ongeveer hoeveel vergelijkingen heeft binair zoeken in het slechtste geval nodig in een gesorteerde array van 1,000,000 elementen?

1. AOngeveer 500,000
2. BOngeveer 1,000
3. COngeveer 100
4. DOngeveer 20

Wat is de looptijd van LSD-radix sort op n gehele getallen met d cijfers in grondtal k?

1. AO(d(n + k))
2. BO(n log n)
3. CO(dn log k)
4. DO(n²)

Waarom is een opzoeking in een hashtabel gemiddeld O(1) maar in het slechtste geval O(n)?

1. AHashfuncties zijn traag
2. BSleutels moeten eerst gesorteerd worden
3. CArrays hebben O(n) toegang
4. DVeel sleutels kunnen in dezelfde bucket botsen

Wat moet je doen om aan te tonen dat een nieuw probleem X NP-moeilijk is?

1. AX in polynomiale tijd reduceren tot een bekend NP-moeilijk probleem
2. BAantonen dat X in polynomiale tijd kan worden geverifieerd
3. CEen bekend NP-moeilijk probleem in polynomiale tijd reduceren tot X
4. DAantonen dat X geen polynomiaal algoritme heeft voor kleine invoer