Werkblad Algoritmen & complexiteit met antwoorden

Hoe heet groei van O(2ⁿ)?

1. AExponentieel
2. BPolynomiaal
3. CLineair
4. DLogaritmisch

Wat is memoisatie?

1. ACommentaar schrijven naast elke regel code
2. BResultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
3. CRecursie automatisch omzetten in een equivalente lus, zodat geen call stack nodig is
4. DGeheugen vrijgeven nadat een functie is teruggekeerd

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

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

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

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

Waarom schakelen veel sorteerroutines in bibliotheken over op insertion sort voor heel kleine deelarrays?

1. ARecursieve algoritmen kunnen geen arrays van minder dan 10 elementen aan
2. BInsertion sort is in het slechtste geval O(n log n)
3. CInsertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
4. DInsertion sort gebruikt voor grote invoer minder geheugen dan elk ander sorteeralgoritme

De tijdcomplexiteit van naïef recursief Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

1. AConstant
2. BLogaritmisch
3. CExponentieel
4. DLineair

Welke grens is juist voor log(n!)?

1. AΘ(n)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(log n)

Welke uitspraak over het selecteren van het k-de kleinste element van een ongesorteerde array is juist?

1. ASelectie is alleen mogelijk in O(n²)
2. BQuickselect loopt in het slechtste geval in O(log n), omdat het maar aan één kant van de pivot recursief verdergaat
3. CQuickselect loopt verwacht in O(n), en median-of-medians garandeert O(n) in het slechtste geval
4. DSelectie heeft altijd Ω(n log n) nodig, omdat er gesorteerd moet worden