Werkblad Algoritmen & complexiteit met antwoorden

Ruimtecomplexiteit meet:

1. AHet aantal regels code
2. BDe hoeveelheid geheugen die een algoritme nodig heeft naarmate de invoer groeit
3. CDe schijfruimte van het programmabestand nadat het is gecompileerd
4. DDe fysieke grootte van de computer

Wat is de grote O van 3n² + 5n + 2?

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

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

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

Wat is de tijdcomplexiteit van het vermenigvuldigen van twee n × n-matrices met de standaard drievoudige lus?

1. AO(n)
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. AInsertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
2. BRecursieve algoritmen kunnen geen arrays van minder dan 10 elementen aan
3. CInsertion sort gebruikt voor grote invoer minder geheugen dan elk ander sorteeralgoritme
4. DInsertion sort is in het slechtste geval O(n log n)

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

1. ADynamisch programmeren werkt alleen op grafenproblemen, niet op arrays
2. BDe deelproblemen overlappen niet, dus er valt niets te hergebruiken
3. CMergesort heeft geen recursieve structuur
4. DMergesort is al O(n)

Wat is de tijdcomplexiteit van het opbouwen van een binaire heap uit n ongesorteerde elementen met de bottom-upmethode?

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

Wat is de looptijd van het algoritme van Dijkstra met een binaire heap op een graaf met V knopen en E kanten?

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