Werkblad Algoritmen & complexiteit met antwoorden

Wat betekent het als een bewerking in O(1) tijd loopt?

1. ADe looptijd groeit niet met de invoergrootte
2. BHet verwerkt precies één element per seconde looptijd
3. CHet kan maar één keer worden uitgevoerd
4. DHet duurt altijd precies één seconde

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

1. AKwadratisch
2. BConstant
3. CLogaritmisch
4. DLineair

Wat is een brute-force-algoritme?

1. AEen algoritme dat willekeurig een antwoord raadt
2. BEen algoritme dat alle mogelijke kandidaatoplossingen probeert
3. CEen algoritme dat altijd recursie gebruikt
4. DEen algoritme dat op veel processoren draait

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

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

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)
2. BO(mn log n)
3. CO(2^m+n)
4. DO(m + n)

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

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

Wat is de oplossing van de recurrente betrekking T(n) = 2T(n/2) + n log n?

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

Het algoritme van Held-Karp voor dynamisch programmeren lost het handelsreizigersprobleem exact op. Wat is de looptijd voor n steden?

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