Werkblad Algoritmen & complexiteit met antwoorden

Wat is de tijdcomplexiteit van het vinden van de grootste waarde in een ongesorteerde array van n getallen?

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

Wat is de looptijd van counting sort voor n gehele getallen in het bereik 0 tot k?

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

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

Wat berekent het algoritme van Floyd-Warshall, en hoe snel?

1. AKortste paden vanuit één bronknoop naar alle andere in O(V + E)
2. BKortste paden tussen alle paren knopen in O(V³)
3. CEen minimale opspannende boom in O(E log V)
4. DEen topologische ordening in O(V²)

De recurrente betrekking T(n) = 2T(n/2) + O(n) heeft als oplossing:

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

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

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

Waarom kan het algoritme van Dijkstra verkeerde resultaten geven als sommige kantgewichten negatief zijn?

1. AHet werkt alleen op ongerichte grafen
2. BNegatieve getallen kunnen niet in een prioriteitswachtrij worden opgeslagen
3. CHet raakt bij elke negatieve kant in een oneindige lus
4. DEen knoop is definitief zodra hij wordt uitgehaald, maar een latere negatieve kant kan hem nog een korter pad geven

Met het mastertheorema heeft T(n) = 8T(n/2) + O(n²) als oplossing:

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