Har du någonsin undrat varför ett program du skrev tog så lång tid att köra? Du kanske skulle vilja veta om du kan göra din kod mer effektiv. Att förstå hur kod körs kan ta din kod till nästa nivå. Big-O notation är ett praktiskt verktyg för att beräkna hur effektiv din kod verkligen är.
Vad är Big-O Notation?
Big-O notation ger dig ett sätt att beräkna hur lång tid det tar att köra din kod. Du kan fysiskt tajma hur lång tid det tar att köra din kod, men med den metoden är det svårt att fånga små tidsskillnader. Till exempel är tiden det tar mellan att köra 20 och 50 rader kod väldigt liten. Men i ett stort program kan dessa ineffektiviteter öka.
Big-O notation räknar hur många steg en algoritm måste utföra för att mäta dess effektivitet. Att närma sig din kod på detta sätt kan vara mycket effektivt om du behöver justera din kod för att öka effektiviteten. Big-O-notation gör att du kan mäta olika algoritmer efter antalet steg som krävs för att köra och objektivt jämföra algoritmernas effektivitet.
Hur beräknar du Big-O-notation
Låt oss överväga två funktioner som räknar hur många enskilda strumpor som finns i en låda. Varje funktion tar antalet par strumpor och returnerar antalet individuella strumpor. Koden är skriven i Python, men det påverkar inte hur vi skulle räkna antalet steg.
Algoritm 1:
def sockCounter(numberOfPairs):
individualSocks = 0
for x in range(numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks
Algoritm 2:
def sockCounter(numberOfPairs):
return numberOfPairs * 2
Det här är ett dumt exempel, och du borde enkelt kunna se vilken algoritm som är effektivare. Men för övning, låt oss gå igenom var och en.
Algoritm 1 har många steg:
- Den tilldelar ett värde på noll till variabeln individualSocks. Den tilldelar variabeln i ett värde på ett. Den jämför värdet av i med numberOfPairs. Det lägger till två till individuella strumpor. Det tilldelar det ökade värdet av individualSocks till sig själv. Det ökar i med ett. Den går sedan tillbaka genom steg 3 till 6 i samma antal gånger som (individuella strumpor – 1).
Antalet steg vi måste slutföra för algoritm ett kan uttryckas som:
4n + 2
Det finns fyra steg som vi måste genomföra n gånger. I det här fallet skulle n vara lika med värdet av antal par. Det finns också 2 steg som genomförs en gång.
I jämförelse har algoritm 2 bara ett steg. Värdet på numberOfPairs multipliceras med två. Vi skulle uttrycka det som:
1
Om det inte redan var uppenbart kan vi nu enkelt se att algoritm 2 är mycket effektivare.
Big-O-analys
I allmänhet, när du är intresserad av Big-O-notationen för en algoritm, är du mer intresserad av den övergripande effektiviteten och mindre av den finkorniga analysen av antalet steg. För att förenkla notationen kan vi bara ange effektivitetens storlek.
I exemplen ovan skulle algoritm 2 uttryckas som en:
O(1)
Men algoritm 1 skulle förenklas som:
O(n)
Denna snabba ögonblicksbild berättar hur effektiviteten av algoritm ett är knuten till värdet av n. Ju större antal desto fler steg kommer algoritmen att behöva slutföra.
Linjär kod
Bildkredit: Nick Fledderus/Noun Project
Eftersom vi inte känner till värdet på n är det mer användbart att tänka på hur värdet på n påverkar mängden kod som behöver köras. I algoritm 1 kan vi säga att sambandet är linjärt. Om du plottar antalet steg mot värdet på n får du en rak linje som går uppåt.
Kvadratisk kod
Alla relationer är inte så enkla som det linjära exemplet. Föreställ dig att du har en 2D-matris och du vill söka efter ett värde i matrisen. Du kan skapa en algoritm så här:
def searchForValue(targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
for y in x:
if(y == targetValue):
foundTarget = True
return foundTarget
I det här exemplet beror antalet steg på antalet arrayer i arraySearched och antalet värden i varje array. Så det förenklade antalet steg skulle n * n eller n².
Bildkredit: Nick Fledderus/Noun Project
Detta förhållande är ett kvadratiskt samband, vilket innebär att antalet steg i vår algoritm växer exponentiellt med n. I Big-O notation skulle du skriva det som:
O(n²)
Logaritmisk kod
Även om det finns många andra samband, är det sista sambandet vi ska titta på logaritmiska samband. För att fräscha upp ditt minne är loggen för ett tal det exponentvärde som krävs för att nå ett tal givet en bas. Till exempel:
log 2 (8) = 3
Loggen är lika med tre för om vår bas var 2 skulle vi behöva ett exponentvärde på 3 för att komma till talet 8.
Bildkredit: Nick Fledderus/Noun Project
Så, förhållandet till en logaritmisk funktion är motsatsen till ett exponentiellt förhållande. När n ökar krävs färre nya steg för att köra algoritmen.
Vid en första anblick verkar detta kontraintuitivt. Hur kan en algoritms steg växa långsammare än n? Ett bra exempel på detta är binära sökningar. Låt oss överväga en algoritm för att söka efter ett tal i en rad unika värden.
Vi börjar med en array för att söka som är i ordning från minsta till största. Därefter kommer vi att kontrollera värdet i mitten av arrayen. Om ditt nummer är högre kommer vi att utesluta de lägre siffrorna i vår sökning och om siffran var lägre kommer vi att utesluta de högre siffrorna. Nu ska vi titta på mittentalet av de återstående siffrorna. Återigen kommer vi att utesluta hälften av siffrorna baserat på om vårt målvärde är högre eller lägre än mittvärdet. Vi kommer att fortsätta den här processen tills vi hittar vårt mål eller fastställer att det inte finns i listan.
Som du kan se, eftersom binära sökningar eliminerar hälften av de möjliga värdena varje pass, eftersom n blir större, påverkas knappt effekten på antalet gånger vi kontrollerar arrayen. För att uttrycka detta i Big-O-notation skulle vi skriva:
O(log(n))
Vikten av Big-O-notation
Big-O nation ger dig ett snabbt och enkelt sätt att kommunicera hur effektiv en algoritm är. Detta gör det lättare att välja mellan olika algoritmer. Detta kan vara särskilt användbart om du använder en algoritm från ett bibliotek och inte nödvändigtvis vet hur koden ser ut.
När du först lär dig koda börjar du med linjära funktioner. Som du kan se från grafen ovan kommer det att ta dig väldigt långt. Men när du blir mer erfaren och börjar bygga mer komplex kod, börjar effektiviteten bli ett problem. En förståelse för hur du kvantifierar effektiviteten av din kod kommer att ge dig de verktyg du behöver för att börja ställa in den för effektivitet och väga för- och nackdelar med algoritmer.
Om författaren
Jennifer Seaton (21 artiklar publicerade)
J. Seaton är en vetenskapsskribent som specialiserat sig på att bryta ner komplexa ämnen. Hon har en doktorsexamen från University of Saskatchewan; hennes forskning fokuserade på att använda spelbaserat lärande för att öka elevernas engagemang online. När hon inte arbetar hittar du henne när hon läser, spelar tv-spel eller trädgårdsarbete.
Mer från Jennifer Seaton
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
