Complexiteit idee

Wat is de tijdcomplexiteit?

De tijdcomplexiteit beschrijft hoe de uitvoertijd van een algoritme groeit met de invoergrootte.

Wat is de ruimtecomplexiteit?

De ruimtecomplexiteit geeft aan hoeveel geheugen een algoritme nodig heeft in functie van de invoergrootte.

Big O notatie

Big O notatie beschrijft de asymptotische limiet van de tijdcomplexiteit en geeft een bovenlimiet aan.

Voorbeeld van O(1)

Een voorbeeld van O(1) is het ophalen van een element uit een array via zijn index.

Wat is O(n)?

O(n) betekent dat de uitvoertijd lineair toeneemt met de invoergrootte n.

Wat is O(n²)?

O(n²) geeft aan dat de uitvoertijd kwadratisch toeneemt, zoals bij geneste loops.

Wat is een algoritme?

Een algoritme is een gestructureerde reeks stappen voor het oplossen van een probleem.

Wat is een recursief algoritme?

Een recursief algoritme lost een probleem op door zichzelf aan te roepen.

Wat is iteratie?

Iteratie is het herhaaldelijk uitvoeren van een reeks instructies, vaak met behulp van loops.

Geef een voorbeeld van een algoritme.

Een voorbeeld is het sorteeralgoritme QuickSort, dat gebruik maakt van de divide-and-conquer techniek.

Wat is de worst-case complexiteit?

De worst-case complexiteit is de maximale tijd die een algoritme nodig heeft voor de slechtste invoer.

Wat is de beste geval complexiteit?

De beste geval complexiteit is de minimale tijd die nodig is voor de snelste invoer.

Wat is een binaire zoekalgoritme?

Een binaire zoekalgoritme zoekt in een gesorteerde lijst door telkens de helft te elimineren.

Verschil tussen O(n) en O(log n)

O(n) groeit lineair, terwijl O(log n) veel langzamer groeit met grotere invoer.

Vul in: O(n log n) is vaak ___ voor sorteeralgoritmes.

efficiënt.

Wat is de rol van de constante factor in complexiteit?

De constante factor beïnvloedt de snelheid van het algoritme, maar niet de complexiteit zelf.

Wat is asymptotische notatie?

Asymptotische notatie beschrijft het gedrag van een functie naarmate de invoer oneindig groot wordt.

Wat is een greedy algoritme?

Een greedy algoritme maakt de lokaal optimale keuze in de hoop dat deze ook globaal optimaal is.