Big O notation Flashcards
what does the Big O notation provide
Big O notation provides a convenient way to compare the speed of algorithms
Wat is Big O Notatie?
Big O Notatie is een afkorting die wordt gebruikt om de efficiëntie van een algoritme te beschrijven, specifiek hoe de uitvoeringstijd of ruimtebehoeften groeien naarmate de invoergrootte toeneemt.
Wat is de tijdcomplexiteit van een invoeging in een ongeordende array?
O(1) - Constante tijd
Wat betekent O(1)?
O(1) betekent constante tijd, waarbij de benodigde tijd niet verandert met de grootte van de invoer.
Wat is de tijdcomplexiteit van een lineaire zoekopdracht?
O(N) - Lineaire tijd
Wat betekent O(N)?
O(N) betekent lineaire tijd, waarbij de benodigde tijd evenredig groeit met de grootte van de invoer.
Wat is de tijdcomplexiteit van een binaire zoekopdracht?
O(log N) - Logaritmische tijd
Wat betekent O(log N)?
O(log N) betekent logaritmische tijd, waarbij de benodigde tijd logaritmisch groeit met de grootte van de invoer.
Wat is de tijdcomplexiteit van een invoeging in een geordende array?
O(N) - Lineaire tijd
Wat is de tijdcomplexiteit van een verwijdering in een ongeordende array?
O(N) - Lineaire tijd
Wat is de tijdcomplexiteit van een verwijdering in een geordende array?
O(N) - Lineaire tijd
Wat betekent O(N^2)?
O(N^2) betekent kwadratische tijd, waarbij de benodigde tijd kwadratisch groeit met de grootte van de invoer.
Wat is de tijdcomplexiteit van een bubblesort?
O(N^2) - Kwadratische tijd
Wat betekent O(N log N)?
O(N log N) betekent dat de benodigde tijd groeit in een patroon dat evenredig is met N keer de logaritme van N.
Wat is de tijdcomplexiteit van een mergesort?
O(N log N) - Log-lineaire tijd
Welke notatie wordt gebruikt voor de tijdcomplexiteit van quicksort in het gemiddelde geval?
O(N log N) - Log-lineaire tijd
Wat is de beste tijdcomplexiteit die haalbaar is voor vergelijkingsgebaseerde sorteeralgoritmen?
O(N log N) - Log-lineaire tijd
Wat is de tijdcomplexiteit van een algoritme dat vereist dat elke mogelijke paar elementen in een array wordt gecontroleerd?
O(N^2) - Kwadratische tijd
Welke notatie vertegenwoordigt een algoritme waarvan de tijdsbehoefte exponentieel groeit met de invoergrootte?
O(2^N) - Exponentiële tijd
Wat is de tijdcomplexiteit van een recursieve berekening van de Fibonacci-reeks?
O(2^N) - Exponentiële tijd
Wat is de tijdcomplexiteit van het toegang krijgen tot een element in een array via index?
O(1) - Constante tijd
Plaats de volgende Big O notaties in volgorde van de beste naar de slechtste tijdcomplexiteit:
1.O(N)
2.O(1)
3.O(N^2)
4.O(log N)
5.O(2^N)
6.O(N log N)
De juiste volgorde van beste naar slechtste tijdcomplexiteit is:
O(1) - Constant time
O(log N) - Logarithmic time
O(N) - Linear time
O(N log N) - Linearithmic time
O(N^2) - Quadratic time
O(2^N) - Exponential time
