Vad är Big-O-notering?

Har du någonsin undrat varför ett program du skrev tog så lång tid att köra? Du kanske vill 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-notering är ett praktiskt verktyg för att beräkna hur effektiv din kod verkligen är.

Vad är Big-O-notering?

Big-O-notering ger dig ett sätt att beräkna hur lång tid det tar att köra din kod. Du kan fysiskt tida hur lång tid det tar för din kod att köra, 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 mycket liten. Men i ett stort program kan dessa ineffektiviteter öka.

Big-O-notering 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 effektiv om du behöver ställa in din kod för att öka effektiviteten. Big-O-notering 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-notering

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 enskilda 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
för x inom intervallet (numberOfPairs):
individualSocks = individualSocks + 2
returnera individualSocks

Algoritm 2:

def sockCounter (numberOfPairs):
returnummerOfPairs * 2

Detta är ett dumt exempel, och du bör lätt kunna berätta vilken algoritm som är effektivare. Men för övning, låt oss springa igenom var och en.

RELATERAD: Vad är en funktion i programmering?

Vad är en funktion i programmering?

Om du lär dig att programmera din egen kod måste du förstå vilka funktioner som är.

Algoritm 1 har många steg:

1. Det tilldelar värdet noll till variabeln individualSocks.
2. Det tilldelar variabeln i ett värde på ett.
3. Det jämför värdet på i till numberOfPairs.
4. Det lägger till två till individualSocks.
5. Det tilldelar det ökade värdet av individualSocks till sig själv.
6. Det ökar i med en.
7. Det går sedan tillbaka genom steg 3 till 6 under samma antal gånger som (indiviualSocks - 1).

Antalet steg som vi måste slutföra för algoritm ett kan uttryckas som:

4n + 2

Det finns fyra steg som vi måste slutföra n gånger. I det här fallet skulle n vara lika med värdet på numberOfPairs. Det finns också två steg som slutförs en gång.

Som 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 lätt se att algoritm 2 är mer effektiv.

Big-O-analys

I allmänhet, när du är intresserad av Big-O-noteringen av en algoritm, är du mer intresserad av den totala effektiviteten och mindre så av finkornig analys av antalet steg. För att förenkla noteringen kan vi bara ange storleken på effektiviteten.

I exemplen ovan skulle algoritm 2 uttryckas som en:

O (1)

Men algoritm 1 skulle förenklas som:

På)

Den här snabba ögonblicksbilden berättar hur effektiviteten hos algoritm en är knuten till värdet av n. Ju större antal desto fler steg behöver algoritmen slutföra.

Linjär kod

Eftersom vi inte vet 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 förhållandet är linjärt. Om du planerar antalet steg vs. värdet på n får du en rak linje som går upp.

Kvadratisk kod

Inte alla relationer är lika enkla som det linjära exemplet. Tänk dig att du har en 2D-array och att du vill söka efter ett värde i arrayen. Du kan skapa en algoritm så här:

def searchForValue (targetValue, arraySearched):
foundTarget = Falskt
för x i matris Sökte:
för y i x:
if (y == targetValue):
foundTarget = True
return foundTarget

I det här exemplet beror antalet steg på antalet matriser i arraySearched och antalet värden i varje array. Så det förenklade antalet steg skulle vara n * n eller n².

Denna relation är en kvadratisk relation, vilket innebär att antalet steg i vår algoritm växer exponentiellt med n. I Big-O-notationen skulle du skriva det som:

O (n²)

RELATERAD: Användbara verktyg för att kontrollera, rengöra och optimera CSS-filer

Logaritmisk kod

Även om det finns många andra relationer, är det sista förhållandet vi ser på logaritmiska förhållanden. För att uppdatera ditt minne är loggen för ett nummer det exponentvärde som krävs för att nå ett nummer som ges 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 siffran 8.

Så, förhållandet mellan 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 nummer i en rad unika värden.

• Vi börjar med en matris att söka i ordningen minsta till största.
• Därefter kommer vi att kontrollera värdet i mitten av matrisen.
• Om ditt nummer är högre kommer vi att utesluta de lägre siffrorna i vår sökning och om antalet var lägre kommer vi att utesluta de högre siffrorna.
• Nu ska vi titta på mitten 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 medelvärdet.
• Vi fortsätter den här processen tills vi hittar vårt mål eller bestämmer 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 gång, när n blir större, påverkas effekten av antalet gånger vi kontrollerar arrayen knappt. För att uttrycka detta i Big-O-notationen skulle vi skriva:

O (log (n))

Betydelsen av Big-O-notering

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 att koda börjar du med linjära funktioner. Som du kan se i diagrammet 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 effektivitet bli ett problem. En förståelse för hur man kvantifierar effektiviteten i 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.

De 10 vanligaste programmerings- och kodfelen

Kodningsfel kan leda till så många problem. Dessa tips hjälper dig att undvika programmeringsfel och hålla din kod meningsfull.

Om författaren