Hoofdstuk 2 Flashcards
1
Q
Welke 3 cases van een algoritme worden onderzocht
A
Beste case running time,
worst case running time,
average case running time
Worst case is het belangrijkste, algoritmen zal nooit slechter performen. Gemiddeld is moeilijk te bepalen.
2
Q
Wat is P en NP
A
P = alle problemen die oplosbaar zijn in polynomiale tijd
NP = nondeterministic polynomial = Alle problemen waarvan de oplossing te verifieeren valt in polynomiale tijd.
3
Q
Wat zijn de nadelen van een asymptotische benadering?
A
Constante spelen geen rol. Twee algoritmen kunnen dezelfde asymptotisch gedrag hebben maar niet even snel zijn
De benadering geldt enkel voor algoritmen met voldoende gegevens (n).
De asymptotische bovengrens van het slechtste geval kan soms te pessimistisch zijn, of heel zeldzaam
4
Q
A
