algorithm
Big-O Notation
Sök…
Anmärkningar
Definition
Big-O-notationen är kärnan en matematisk notation, som används för att jämföra konvergensgraden för funktioner. Låt n -> f(n) och n -> g(n) vara funktioner som definieras över de naturliga siffrorna. Då säger vi att f = O(g) om och bara om f(n)/g(n) är avgränsat när n närmar sig oändligheten. Med andra ord, f = O(g) om och bara om det finns en konstant A, så att för alla n, f(n)/g(n) <= A
Faktiskt omfattningen av Big-O-notationen är lite bredare i matematik, men för enkelhetens skull har jag begränsat det till vad som används i algoritmkomplexitetsanalys: funktioner definierade på naturalerna, som har icke-nollvärden och fallet med att växa till oändligheten.
Vad betyder det ?
Låt oss ta f(n) = 100n^2 + 10n + 1 och g(n) = n^2 . Det är helt klart att båda dessa funktioner tenderar till oändlighet eftersom n tenderar till oändlighet. Men ibland räcker det inte med att känna till gränsen, och vi vill också veta hur snabbt funktionerna närmar sig deras gräns. Begrepp som Big-O hjälper till att jämföra och klassificera funktioner efter deras konvergenshastighet.
Låt oss ta reda på om f = O(g) genom att använda definitionen. Vi har f(n)/g(n) = 100 + 10/n + 1/n^2 . Sedan 10/n är 10 när n är 1 och minskar, och sedan 1/n^2 är ett när n är 1 och är också minskar, har vi f f(n)/g(n) <= 100 + 10 + 1 = 111 . Definitionen är nöjd eftersom vi har hittat en gräns av f(n)/g(n) (111) och så f = O(g) (vi säger att f är en Big-O för n^2 ).
Detta betyder att f tenderar till oändligheten med ungefär samma hastighet som g. Nu kan det tyckas vara en konstig sak att säga, för vad vi har funnit är att f är högst 111 gånger större än g, eller med andra ord när g växer med 1, f växer med högst 111. Det kan verka som växande 111 gånger snabbare är inte "ungefär samma hastighet". Och faktiskt är Big-O-notationen inte ett mycket exakt sätt att klassificera funktionskonvergenshastighet, varför vi i matematik använder ekvivalensförhållandet när vi vill ha en exakt uppskattning av hastighet. Men för att separera algoritmer i stora hastighetsklasser räcker Big-O. Vi behöver inte separera funktioner som växer ett fast antal gånger snabbare än varandra, utan bara funktioner som växer oändligt snabbare än varandra. Om vi till exempel tar h(n) = n^2*log(n) ser vi att h(n)/g(n) = log(n) som tenderar att oändligt med n så h inte är O (n ^ 2), eftersom h växer oändligt snabbare än n ^ 2.
Nu måste jag göra en sidnotis: du kanske har lagt märke till att om f = O(g) och g = O(h) , så är f = O(h) . Till exempel i vårt fall har vi f = O(n^3) och f = O(n^4) ... I algoritmkomplexitetsanalys säger vi ofta f = O(g) att betyda att f = O(g) och g = O(f) , som kan förstås som "g är den minsta Big-O för f". I matematik säger vi att sådana funktioner är Big-Thetas av varandra.
Hur används det?
Vid jämförelse av algoritmprestanda är vi intresserade av antalet operationer som en algoritm utför. Detta kallas tidskomplexitet . I den här modellen anser vi att varje grundläggande operation (tillägg, multiplikation, jämförelse, tilldelning etc.) tar en fast tid och vi räknar antalet sådana operationer. Vi kan vanligtvis uttrycka detta nummer som en funktion av inmatningens storlek, som vi kallar n. Och tyvärr växer detta nummer oftast till oändlighet med n (om det inte gör det, säger vi att algoritmen är O (1)). Vi separerar våra algoritmer i stora hastighetsklasser definierade av Big-O: när vi talar om en "O (n ^ 2) algoritm", menar vi att antalet operationer det utför, uttryckt som en funktion av n, är en O ( n ^ 2). Detta säger att vår algoritm är ungefär lika snabb som en algoritm som skulle göra ett antal operationer lika med kvadratet på storleken på dess ingång, eller snabbare . Den "eller snabbare" delen är där för att jag använde Big-O istället för Big-Theta, men vanligtvis säger folk Big-O för att betyda Big-Theta.
När vi räknar operationer överväger vi vanligtvis det värsta fallet: till exempel om vi har en slinga som kan köras högst n gånger och som innehåller 5 operationer är antalet operationer vi räknar 5n. Det är också möjligt att överväga den genomsnittliga fallkomplexiteten.
Snabbanmärkning: en snabb algoritm är en som utför få operationer, så om antalet operationer växer till oändlighet snabbare , då är algoritmen långsammare : O (n) är bättre än O (n ^ 2).
Vi är ibland intresserade av rymdkomplexiteten i vår algoritm. För detta betraktar vi antalet byte i minnet som upptas av algoritmen som en funktion av ingångsstorleken och använder Big-O på samma sätt.
En enkel slinga
Följande funktion hittar det maximala elementet i en matris:
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;
}
Ingångsstorleken är storleken på matrisen, som jag kallade len i koden.
Låt oss räkna operationerna.
int max = INT_MIN;
size_t i = 0;
Dessa två uppdrag görs bara en gång, så det är två operationer. De operationer som är slingade är:
if (max < array[i])
i++;
max = array[i]
Eftersom det finns 3 operationer i slingan, och slingan görs n gånger, lägger vi till 3n till våra redan befintliga 2 operationer för att få 3n + 2 . Så vår funktion tar 3n + 2 operationer för att hitta max (dess komplexitet är 3n + 2 ). Detta är ett polynom där den snabbast växande termen är en faktor av n, så det är O (n).
Du har antagligen lagt märke till att "operation" inte är särskilt väl definierad. Till exempel sa jag att if (max < array[i]) var en operation, men beroende på arkitekturen kan detta uttalande sammanställas till exempel tre instruktioner: ett minne läst, en jämförelse och en gren. Jag har också betraktat alla operationer som samma, även om minnesoperationerna till exempel kommer att vara långsammare än de andra, och deras prestanda kommer att variera mycket beroende på t.ex. cache-effekter. Jag har också helt ignorerat returrättet, det faktum att en ram kommer att skapas för funktionen osv. I slutändan spelar det ingen roll för komplexitetsanalysen, för vilket sätt jag väljer att räkna operationer kommer det bara att ändra koefficienten av n-faktorn och konstanten, så resultatet blir fortfarande O (n). Komplexitet visar hur algoritmen skalar med ingångens storlek, men det är inte den enda aspekten av prestanda!
En kapslad slinga
Följande funktion kontrollerar om en matris har några duplikat genom att ta varje element och sedan iterera över hela matrisen för att se om elementet är där
_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;
}
Den inre slingan utför vid varje iteration ett antal operationer som är konstant med n . Den yttre slingan utför också några konstant operationer och kör den inre slingan n gånger. Själva yttre slingan körs n gånger. Så operationerna inuti den inre slingan körs n^2 gånger, operationerna i den yttre slingan körs n gånger och tilldelningen till i görs en gång. Således kommer komplexiteten att vara något som an^2 + bn + c , och eftersom den högsta termen är n^2 , är O-notationen O(n^2) .
Som ni kanske har lagt märke till kan vi förbättra algoritmen genom att undvika att göra samma jämförelse flera gånger. Vi kan börja från i + 1 i den inre slingan, eftersom alla element innan det redan har kontrollerats mot alla arrayelement, inklusive det i indexet i + 1 . Detta gör att vi kan släppa i == j kontrollen.
_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;
}
Självklart gör denna andra version mindre operationer och är därför mer effektiv. Hur översätter det till Big-O-notation? Tja, nu körs den inre slingkroppen 1 + 2 + ... + n - 1 = n(n-1)/2 gånger. Detta är fortfarande ett polynom i den andra graden, och så är det fortfarande bara O(n^2) . Vi har tydligt sänkt komplexiteten, eftersom vi grovt indelas med 2 antalet operationer som vi gör, men vi är fortfarande i samma komplex klass som definieras av Big-O. För att sänka komplexiteten till en lägre klass skulle vi behöva dela antalet operationer med något som tenderar att oändligt med n .
Ett exempel på O (log n)
Introduktion
Tänk på följande problem:
L är en sorterad lista som innehåller n signerade heltal ( n är tillräckligt stor), till exempel [-5, -2, -1, 0, 1, 2, 4] (här har n värdet 7). Om L är känt för att innehålla heltalet 0, hur hittar du indexet 0?
Naiv inställning
Det första som kommer att tänka på är att bara läsa varje index tills 0 hittas. I värsta fall är antalet operationer n , så komplexiteten är O (n).
Det här fungerar bra för små värden på n , men finns det ett mer effektivt sätt?
Dikotomi
Tänk på följande algoritm (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 och b är indexen mellan vilka 0 är att hitta. Varje gång vi går in i slingan använder vi ett index mellan a och b och använder det för att begränsa det område som ska sökas.
I värsta fall måste vi vänta tills a och b är lika. Men hur många operationer tar det? Inte n, för varje gång vi går in i slingan delar vi avståndet mellan a och b med ungefär två. Snarare är komplexiteten O (log n).
Förklaring
Obs: När vi skriver "log" menar vi den binära logaritmen eller logbas 2 (som vi kommer att skriva "log_2"). Som O (log_2 n) = O (log n) (du kan göra matematik) kommer vi att använda "log" istället för "log_2".
Låt oss ringa x antalet operationer: vi vet att 1 = n / (2 ^ x).
Så 2 ^ x = n, sedan x = log n
Slutsats
Kom ihåg att komplexiteten är logaritmisk när du står inför successiva uppdelningar (vare sig det är två eller med valfritt antal).
O (log n) typer av algoritmer
Låt oss säga att vi har problem med storlek n. För varje steg i vår algoritm (som vi behöver skriva) blir vårt ursprungliga problem hälften av dess tidigare storlek (n / 2).
Så vid varje steg blir vårt problem hälften.
| Steg | Problem |
|---|---|
| 1 | n / 2 |
| 2 | n / 4 |
| 3 | n / 8 |
| 4 | n / 16 |
När problemutrymmet reduceras (dvs. löses fullständigt) kan det inte minskas ytterligare (n blir lika med 1) efter att ha lämnat kontrolltillståndet.
Låt oss säga på kth-steget eller antalet operationer:
problem-storlek = 1
Men vi vet att i kth-steget bör vår problemstorlek vara:
problemstorlek = n / 2 k
Från 1 och 2:
n / 2 k = 1 eller
n = 2 k
Ta loggen på båda sidor
log e n = k log e 2
eller
k = log e n / log e 2
Använda formellogg x m / log x n = log n m
k = log 2 n
eller helt enkelt k = log n
Nu vet vi att vår algoritm kan köras maximalt upp till log n, följaktligen kommer tidskomplexiteten
O (log n)
Ett mycket enkelt exempel på kod för att stödja texten ovan är:
for(int i=1; i<=n; i=i*2)
{
// perform some operation
}
Så nu om någon frågar dig om n är 256 hur många steg som slingan (eller någon annan algoritm som skär ner sin problemstorlek till hälften) kommer att köras kan du mycket enkelt beräkna.
k = log 2 256
k = log 2 2 8 (=> log a a = 1)
k = 8
Ett annat mycket bra exempel på liknande fall är Binary Search Algoritm .
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
}
