Werkblad Algoritmen & complexiteit met antwoorden

De looptijd van een algoritme is O(n). Hoe heet deze groei?

1. ALineair
2. BLogaritmisch
3. CConstant
4. DKwadratisch

Welke van deze looptijden is polynomiaal?

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

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

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

Met munten van 1, 3 en 4 en een bedrag van 6: hoeveel munten gebruikt de gulzige methode "grootste munt eerst", vergeleken met het optimum?

1. AGulzig gebruikt 3 munten; het optimum is 3
2. BGulzig gebruikt 3 munten; het optimum is 2
3. CGulzig gebruikt 2 munten; het optimum is 2
4. DGulzig gebruikt 4 munten; het optimum is 3

Welke uitspraak over een recursieve functie zonder bereikbaar basisgeval is juist?

1. AZe loopt in O(1) tijd
2. BZe geeft automatisch 0 terug
3. CDe compiler maakt er altijd een lus van die veilig eindigt
4. DZe blijft zichzelf aanroepen totdat de call stack overloopt

Wat is de tijdcomplexiteit van het standaardalgoritme voor dynamisch programmeren voor de langste gemeenschappelijke deelrij van strings met lengte m en n?

1. AO(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

Wat is de tijdcomplexiteit van: for i = 1 to n: for (j = i; j ≤ n; j = j + i) doe O(1) werk?

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

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

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