Werkblad Algoritmen & complexiteit met antwoorden

Een element in een array via de index benaderen kost:

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

Welke van deze looptijden is polynomiaal?

1. AO(n³)
2. BO(n!)
3. CO(2ⁿ)
4. DO(nⁿ)

Hoe werkt selection sort?

1. AHet splitst de array in helften en voegt die samen
2. BHet voegt elk element door verschuiven in een groeiend gesorteerd deel in
3. CHet zoekt steeds het minimum van het ongesorteerde deel en verwisselt het naar voren
4. DHet verwisselt steeds naast elkaar liggende elementen die in de verkeerde volgorde staan

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

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

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

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

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

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

Waarom heeft elke zoekmethode op basis van vergelijkingen in een gesorteerde array in het slechtste geval Ω(log n) vergelijkingen nodig?

1. AEen beslisboom met n mogelijke uitkomsten moet een diepte van minstens log₂ n hebben
2. BBinair zoeken is het enige mogelijke algoritme en heeft log₂ n vergelijkingen nodig
3. CElke vergelijking kost logaritmische tijd
4. DElk element moet minstens één keer worden vergeleken

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