algorithm
Big-O-notatie
Zoeken…
Opmerkingen
Definitie
De Big-O-notatie is in de kern een wiskundige notatie, die wordt gebruikt om de mate van convergentie van functies te vergelijken. Laat n -> f(n) en n -> g(n) worden functies gedefinieerd over de natuurlijke getallen. Dan zeggen we dat f = O(g) als en alleen als f(n)/g(n) begrensd is wanneer n oneindig nadert. Met andere woorden, f = O(g) als en alleen als er een constante A bestaat, zodat voor alle n, f(n)/g(n) <= A
Eigenlijk is het bereik van de Big-O-notatie een beetje breder in de wiskunde, maar voor de eenvoud heb ik het beperkt tot wat wordt gebruikt in algoritmecomplexiteitsanalyse: functies die zijn gedefinieerd op de natuur, die niet-nulwaarden hebben, en het geval van n groeien tot het oneindige.
Wat betekent het ?
Laten we het geval nemen van f(n) = 100n^2 + 10n + 1 en g(n) = n^2 . Het is vrij duidelijk dat beide functies neigen naar oneindig omdat n neigt naar oneindig. Maar soms is het niet voldoende om de limiet te kennen en willen we ook weten hoe snel de functies hun limiet naderen. Begrippen als Big-O helpen functies te vergelijken en te classificeren op basis van hun snelheid van convergentie.
Laten we kijken of f = O(g) door de definitie toe te passen. We hebben f(n)/g(n) = 100 + 10/n + 1/n^2 . Aangezien 10/n 10 wanneer n 1 is en afneemt, en aangezien 1/n^2 1 is als n 1 is en ook afneemt, we f f(n)/g(n) <= 100 + 10 + 1 = 111 . Aan de definitie is voldaan omdat we een grens hebben gevonden van f(n)/g(n) (111) en dus f = O(g) (we zeggen dat f een Big-O is van n^2 ).
Dit betekent dat f neigt naar oneindig met ongeveer dezelfde snelheid als g. Dit lijkt misschien een vreemd iets om te zeggen, omdat we hebben gevonden dat f maximaal 111 keer groter is dan g, of met andere woorden wanneer g met 1 groeit, f met maximaal 111 groeit. Het lijkt misschien dat groeiend 111 keer sneller is niet "ongeveer dezelfde snelheid". En inderdaad de Big-O notatie is niet een erg nauwkeurige manier in te delen functie convergentie snelheid, dat is de reden waarom in de wiskunde het gebruiken we equivalentie relatie toen we een precieze schatting van de snelheid. Maar om algoritmen in grote snelheidsklassen te scheiden, is Big-O voldoende. We hoeven geen functies te scheiden die een vast aantal keren sneller groeien dan elkaar, maar alleen functies die oneindig sneller groeien dan elkaar. Als we bijvoorbeeld h(n) = n^2*log(n) , zien we dat h(n)/g(n) = log(n) die neigt naar oneindig met n zodat h niet O is (n ^ 2), omdat h oneindig sneller groeit dan n ^ 2.
Nu moet ik een kanttekening maken: je hebt misschien gemerkt dat als f = O(g) en g = O(h) , dan f = O(h) . In ons geval hebben we bijvoorbeeld f = O(n^3) en f = O(n^4) ... In algoritmecomplexiteitsanalyse zeggen we vaak dat f = O(g) betekent dat f = O(g) en g = O(f) , wat kan worden begrepen als "g is de kleinste Big-O voor f". In de wiskunde zeggen we dat dergelijke functies Big-Thetas van elkaar zijn.
Hoe gebruik je het ?
Bij het vergelijken van algoritmeprestaties zijn we geïnteresseerd in het aantal bewerkingen dat een algoritme uitvoert. Dit wordt tijdcomplexiteit genoemd . In dit model zijn we van mening dat elke basisbewerking (optellen, vermenigvuldigen, vergelijken, toewijzen, enz.) Een vaste hoeveelheid tijd kost en we tellen het aantal van dergelijke bewerkingen. We kunnen dit getal meestal uitdrukken als functie van de grootte van de invoer, die we n noemen. En helaas groeit dit aantal meestal tot oneindig met n (als dit niet het geval is, zeggen we dat het algoritme O (1) is). We scheiden onze algoritmen in grote snelheidsklassen gedefinieerd door Big-O: wanneer we spreken over een "O (n ^ 2) algoritme", bedoelen we dat het aantal bewerkingen dat het uitvoert, uitgedrukt als een functie van n, een O ( n ^ 2). Dit zegt dat ons algoritme ongeveer even snel is als een algoritme dat een aantal bewerkingen zou doen gelijk aan het kwadraat van de invoer, of sneller . Het "of snellere" deel is er omdat ik Big-O gebruikte in plaats van Big-Theta, maar meestal zeggen mensen dat Big-O Big-Theta betekent.
Bij het tellen van operaties beschouwen we meestal het slechtste geval: als we bijvoorbeeld een lus hebben die maximaal n keer kan worden uitgevoerd en die 5 operaties bevat, is het aantal operaties dat we tellen 5n. Het is ook mogelijk om de gemiddelde case-complexiteit te overwegen.
Snelle opmerking: een snel algoritme is er een die weinig bewerkingen uitvoert, dus als het aantal bewerkingen sneller tot oneindig groeit, is het algoritme langzamer : O (n) is beter dan O (n ^ 2).
We zijn soms ook geïnteresseerd in de ruimte complexiteit van ons algoritme. Hiervoor beschouwen we het aantal bytes in het geheugen dat wordt ingenomen door het algoritme als een functie van de grootte van de invoer en gebruiken we Big-O op dezelfde manier.
Een eenvoudige lus
De volgende functie vindt het maximale element in een array:
int find_max(const int *array, size_t len) {
int max = INT_MIN;
for (size_t i = 0; i < len; i++) {
if (max < array[i]) {
max = array[i];
}
}
return max;
}
De invoergrootte is de grootte van de array, die ik in de code len noemde.
Laten we de operaties tellen.
int max = INT_MIN;
size_t i = 0;
Deze twee opdrachten worden slechts eenmaal uitgevoerd, dus dat zijn 2 bewerkingen. De bewerkingen die worden doorgelust zijn:
if (max < array[i])
i++;
max = array[i]
Aangezien er 3 bewerkingen in de lus zijn en de lus n keer wordt gedaan, voegen we 3n aan onze reeds bestaande 2 bewerkingen om 3n + 2 te krijgen. Dus onze functie heeft 3n + 2 bewerkingen nodig om het maximum te vinden (de complexiteit ervan is 3n + 2 ). Dit is een polynoom waarbij de snelstgroeiende term een factor n is, dus O (n).
Je hebt waarschijnlijk gemerkt dat "operatie" niet erg goed is gedefinieerd. Ik zei bijvoorbeeld dat if (max < array[i]) één bewerking was, maar afhankelijk van de architectuur kan deze verklaring worden gecompileerd tot bijvoorbeeld drie instructies: één geheugen lezen, één vergelijking en één tak. Ik heb ook alle bewerkingen als hetzelfde beschouwd, hoewel de geheugenbewerkingen bijvoorbeeld langzamer zullen zijn dan de andere, en hun prestaties enorm zullen variëren vanwege bijvoorbeeld cache-effecten. Ik heb ook de return-instructie, het feit dat een frame voor de functie wordt gemaakt, enz. Volledig genegeerd. van de n-factor en de constante, dus het resultaat is nog steeds O (n). Complexiteit laat zien hoe het algoritme schaalt met de grootte van de invoer, maar het is niet het enige aspect van de prestaties!
Een geneste lus
De volgende functie controleert of een array duplicaten bevat door elk element te nemen en vervolgens de hele array te doorlopen om te zien of het element aanwezig is
_Bool contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len; j++) {
if (i != j && array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
De binnenlus voert bij elke iteratie een aantal bewerkingen uit die constant is met n . De buitenste lus voert ook een paar constante bewerkingen uit en loopt de binnenste lus n keer. De buitenste lus zelf wordt n keer uitgevoerd. De bewerkingen in de binnenste lus worden dus n^2 keer uitgevoerd, de bewerkingen in de buitenste lus worden n keer uitgevoerd en de toewijzing aan i wordt één keer uitgevoerd. De complexiteit zal dus zoiets zijn als an^2 + bn + c , en omdat de hoogste term n^2 , is de O-notatie O(n^2) .
Zoals je misschien hebt gemerkt, kunnen we het algoritme verbeteren door te vermijden dat we dezelfde vergelijkingen meerdere keren moeten doen. We kunnen beginnen met i + 1 in de binnenste lus, omdat alle elementen ervoor al zijn gecontroleerd aan de hand van alle array-elementen, inclusief die in index i + 1 . Hiermee kunnen we de i == j cheque laten vallen.
_Bool faster_contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
Het is duidelijk dat deze tweede versie minder bewerkingen uitvoert en dus efficiënter is. Hoe vertaalt zich dat in Big-O-notatie? Welnu, nu wordt het lichaam van de binnenste lus 1 + 2 + ... + n - 1 = n(n-1)/2 keer uitgevoerd. Dit is nog steeds een polynoom van de tweede graad, en dus nog steeds alleen O(n^2) . We hebben duidelijk verlaagde de complexiteit, aangezien we grofweg verdeeld door 2 het aantal operaties dat we aan het doen zijn, maar we zijn nog steeds in dezelfde complexiteit klasse zoals gedefinieerd door Big-O. Om de complexiteit tot een lagere klasse te verlagen, moeten we het aantal bewerkingen delen door iets dat de neiging heeft tot oneindig met n .
Een O (log n) -voorbeeld
Invoering
Overweeg het volgende probleem:
L is een gesorteerde lijst met n integers ( n zijn groot genoeg), bijvoorbeeld [-5, -2, -1, 0, 1, 2, 4] (hier, n heeft een waarde van 7). Als bekend is dat L het gehele getal 0 bevat, hoe kun je dan de index van 0 vinden?
Naïeve aanpak
Het eerste wat u te binnen schiet is om elke index te lezen totdat 0 wordt gevonden. In het ergste geval is het aantal bewerkingen n , dus de complexiteit is O (n).
Dit werkt prima voor kleine waarden van n , maar is er een efficiëntere manier?
Dichotomie
Overweeg het volgende algoritme (Python3):
a = 0
b = n-1
while True:
h = (a+b)//2 ## // is the integer division, so h is an integer
if L[h] == 0:
return h
elif L[h] > 0:
b = h
elif L[h] < 0:
a = h
a en b zijn de indexen waartussen 0 moet worden gevonden. Elke keer dat we de lus binnengaan, gebruiken we een index tussen a en b en gebruiken we deze om het te doorzoeken gebied te verkleinen.
In het ergste geval moeten we wachten tot a en b gelijk zijn. Maar hoeveel operaties kost dat? Niet n, want elke keer dat we de lus ingaan, delen we de afstand tussen a en b door ongeveer twee. De complexiteit is eerder O (log n).
Uitleg
Opmerking: Wanneer we "log" schrijven, bedoelen we de binaire logaritme of log base 2 (die we "log_2" zullen schrijven). Als O (log_2 n) = O (log n) (u kunt de wiskunde doen) zullen we "log" gebruiken in plaats van "log_2".
Laten we x het aantal bewerkingen noemen: we weten dat 1 = n / (2 ^ x).
Dus 2 ^ x = n en vervolgens x = log n
Conclusie
Onthoud dat de complexiteit logaritmisch is wanneer u wordt geconfronteerd met opeenvolgende delingen (zij het met twee of met een willekeurig aantal).
O (log n) soorten algoritmen
Laten we zeggen dat we een probleem hebben met maat n. Nu voor elke stap van ons algoritme (die we moeten schrijven), wordt ons oorspronkelijke probleem de helft van de vorige grootte (n / 2).
Dus bij elke stap wordt ons probleem de helft.
| Stap | Probleem |
|---|---|
| 1 | n / 2 |
| 2 | n / 4 |
| 3 | n / 8 |
| 4 | n / 16 |
Wanneer de probleemruimte is verkleind (dwz volledig is opgelost), kan deze niet verder worden verkleind (n wordt gelijk aan 1) na het verlaten van de controleconditie.
Laten we zeggen bij stap of aantal bewerkingen:
probleemgrootte = 1
Maar we weten dat we in kth step onze probleemgrootte moeten zijn:
probleemgrootte = n / 2 k
Van 1 en 2:
n / 2 k = 1 of
n = 2 k
Neem log aan beide kanten
log e n = k log e 2
of
k = log e n / log e 2
Formule log x m / log x n = log n m gebruiken
k = log 2 n
of gewoon k = log n
Nu weten we dat ons algoritme maximaal tot log n kan lopen, vandaar dat tijdcomplexiteit als volgt komt
O (log n)
Een heel eenvoudig voorbeeld in code ter ondersteuning van bovenstaande tekst is:
for(int i=1; i<=n; i=i*2)
{
// perform some operation
}
Dus als iemand je nu vraagt of n 256 is, hoeveel stappen die lus (of een ander algoritme dat de probleemgrootte tot de helft beperkt) zal doorlopen, kun je heel gemakkelijk berekenen.
k = log 2 256
k = log 2 2 8 (=> log a a = 1)
k = 8
Een ander zeer goed voorbeeld voor een vergelijkbaar geval is Binary Search Algorithm .
int bSearch(int arr[],int size,int item){
int low=0;
int high=size-1;
while(low<=high){
mid=low+(high-low)/2;
if(arr[mid]==item)
return mid;
else if(arr[mid]<item)
low=mid+1;
else high=mid-1;
}
return –1;// Unsuccessful result
}