Werkblad Algoritmen & complexiteit met antwoorden

Wat is de tijdcomplexiteit van diepte-eerst zoeken (DFS) in een graaf die als adjacentielijsten is opgeslagen?

1. AO(V²)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

Een algoritme met twee geneste lussen die elk n keer worden doorlopen, heeft doorgaans welke complexiteit?

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

Wat is de tijdcomplexiteit van lineair zoeken in een ongesorteerde array van n elementen (worst case)?

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

Wat is de tijdcomplexiteit van het algoritme van Bellman-Ford op een graaf met V knopen en E kanten?

1. AO(V × E)
2. BO(E log V)
3. CO(V + E)
4. DO(V³ × E)

Waarom wordt het grondtal van een logaritme in grote-O-notatie meestal weggelaten, zoals in O(log n)?

1. ALogaritmen met verschillende grondtallen verschillen alleen een constante factor
2. BHet grondtal doet er alleen toe voor kleine n
3. CLogaritmen worden altijd afgerond op gehele getallen
4. DAlle logaritmen in de informatica hebben grondtal 10, dus het is impliciet

Een functie voert één lus van n iteraties uit en daarna, los daarvan, nog een lus van n iteraties. Wat is de tijdcomplexiteit?

1. AO(log n)
2. BO(n²)
3. CO(2ⁿ)
4. DO(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, de ondergrens is dus fout
2. BNee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is
3. CJa, maar alleen voor arrays korter dan 100
4. DNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer

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

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