Hvad er Big-O Notation?

Har du nogensinde spekuleret på, hvorfor et program, du skrev, tog så lang tid at køre? Måske vil du gerne vide, om du kan gøre din kode mere effektiv. At forstå, hvordan kode kører, kan bringe din kode til det næste niveau. Big-O-notation er et praktisk værktøj til at beregne, hvor effektiv din kode virkelig er.

Hvad er Big-O Notation?

Big-O-notation giver dig en måde at beregne, hvor lang tid det tager at køre din kode. Du kan fysisk tid, hvor længe din kode tager at køre, men med denne metode er det svært at fange små tidsforskelle. For eksempel er den tid det tager mellem at køre 20 og 50 kodelinjer meget lille. I et stort program kan disse ineffektiviteter imidlertid tilføje sig.

Big-O-notation tæller, hvor mange trin en algoritme skal udføre for at måle dens effektivitet. At nærme sig din kode på denne måde kan være meget effektiv, hvis du har brug for at indstille din kode for at øge effektiviteten. Big-O-notation giver dig mulighed for at måle forskellige algoritmer efter antallet af trin, det kræver at køre, og objektivt sammenligne algoritmernes effektivitet.

Hvordan beregner du Big-O Notation

Lad os overveje to funktioner, der tæller, hvor mange individuelle sokker der er i en skuffe. Hver funktion tager antallet af par sokker og returnerer antallet af individuelle sokker. Koden er skrevet i Python, men det påvirker ikke, hvordan vi ville tælle antallet af trin.

Algoritme 1:

def sockCounter (numberOfPairs):
individualSocks = 0
for x inden for rækkevidde (numberOfPairs):
individualSocks = individualSocks + 2
returner individualSocks

Algoritme 2:

def sockCounter (numberOfPairs):
returnummerOfPairs * 2

Dette er et fjollet eksempel, og du skal være i stand til let at fortælle, hvilken algoritme der er mere effektiv. Men til praksis, lad os løbe igennem hver.

RELATEREDE: Hvad er en funktion i programmering?

Hvad er en funktion i programmering?

Hvis du lærer at programmere din egen kode, skal du forstå, hvad funktionerne er.

Algoritme 1 har mange trin:

1. Den tildeler variablen individualSocks en værdi på nul.
2. Det tildeler en værdi på en til variablen i.
3. Den sammenligner værdien af ​​i med numberOfPairs.
4. Det tilføjer to til individualSocks.
5. Det tildeler den øgede værdi af individualSocks til sig selv.
6. Det forøger jeg i én.
7. Derefter løber den tilbage gennem trin 3 til 6 i det samme antal gange som (indiviualSocks - 1).

Antallet af trin, vi skal gennemføre for algoritme et, kan udtrykkes som:

4n + 2

Der er fire trin, som vi skal udføre n gange. I dette tilfælde ville n svare til værdien af ​​numberOfPairs. Der er også 2 trin, der er afsluttet en gang.

Til sammenligning har algoritme 2 kun et trin. Værdien af ​​numberOfPairs ganges med to. Vi vil udtrykke det som:

1

Hvis det ikke allerede var tydeligt, kan vi nu let se, at algoritme 2 er mere effektiv ganske lidt.

Big-O-analyse

Generelt, når du er interesseret i Big-O-notationen af ​​en algoritme, er du mere interesseret i den samlede effektivitet og mindre så i finkorneanalysen af ​​antallet af trin. For at forenkle notationen kan vi bare angive størrelsen på effektiviteten.

I eksemplerne ovenfor vil algoritme 2 udtrykkes som en:

O (1)

Men algoritme 1 ville være forenklet som:

På)

Dette hurtige øjebliksbillede fortæller os, hvordan effektiviteten af ​​algoritme en er bundet til værdien af ​​n. Jo større antal, jo flere trin skal algoritmen udføre.

Lineær kode

Da vi ikke kender værdien af ​​n, er det mere nyttigt at tænke over, hvordan værdien af ​​n påvirker den mængde kode, der skal køres. I algoritme 1 kan vi sige, at forholdet er lineært. Hvis du tegner antallet af trin vs. værdien af ​​n får du en lige linje, der går op.

Kvadratisk kode

Ikke alle relationer er så enkle som det lineære eksempel. Forestil dig, at du har et 2D-array, og at du gerne vil søge efter en værdi i arrayet. Du kan oprette en algoritme som denne:

def searchForValue (targetValue, arraySearched):
foundTarget = Falsk
til x i matrix
for y i x:
hvis (y == targetValue):
foundTarget = Sandt
return foundTarget

I dette eksempel afhænger antallet af trin af antallet af arrays i arraySearched og antallet af værdier i hver array. Så det forenklede antal trin ville være n * n eller n².

Dette forhold er et kvadratisk forhold, hvilket betyder, at antallet af trin i vores algoritme vokser eksponentielt med n. I Big-O notation ville du skrive det som:

O (n²)

RELATEREDE: Nyttige værktøjer til at kontrollere, rense og optimere CSS-filer

Logaritmisk kode

Selvom der er mange andre forhold, er det sidste forhold, vi vil se på, logaritmiske forhold. For at opdatere din hukommelse er loggen på et nummer den eksponentværdi, der kræves for at nå et tal, der får en base. For eksempel:

log 2 (8) = 3

Loggen er lig med tre, for hvis vores base var 2, ville vi have brug for en eksponentværdi på 3 for at komme til tallet 8.

Så forholdet mellem en logaritmisk funktion er det modsatte af et eksponentielt forhold. Når n stiger, kræves der færre nye trin for at køre algoritmen.

Ved første øjekast virker dette kontraintuitivt. Hvordan kan en algoritmes trin vokse langsommere end n? Et godt eksempel på dette er binære søgninger. Lad os overveje en algoritme til at søge efter et tal i en række unikke værdier.

• Vi starter med en matrix til søgning, der er i rækkefølge fra mindste til største.
• Dernæst vil vi kontrollere værdien i midten af ​​arrayet.
• Hvis dit nummer er højere, udelukker vi de lavere tal i vores søgning, og hvis antallet var lavere, vil vi ekskludere de højere tal.
• Nu skal vi se på det midterste nummer på de resterende tal.
• Igen udelukker vi halvdelen af ​​antallet baseret på, om vores målværdi er højere eller lavere end den midterste værdi.
• Vi fortsætter denne proces, indtil vi finder vores mål eller bestemmer, at det ikke er på listen.

Som du kan se, da binære søgninger eliminerer halvdelen af ​​de mulige værdier hvert pass, når n bliver større, påvirkes effekten næppe af antallet af gange, vi kontrollerer arrayet. For at udtrykke dette i Big-O notation ville vi skrive:

O (log (n))

Betydningen af ​​Big-O Notation

Big-O nation giver dig en hurtig og nem måde at kommunikere, hvor effektiv en algoritme er. Dette gør det lettere at vælge mellem forskellige algoritmer. Dette kan være særligt nyttigt, hvis du bruger en algoritme fra et bibliotek og ikke nødvendigvis ved, hvordan koden ser ud.

Når du først lærer at kode, begynder du med lineære funktioner. Som du kan se fra grafen ovenfor, kommer det dig meget langt. Men når du bliver mere erfaren og begynder at opbygge mere kompleks kode, begynder effektivitet at blive et problem. En forståelse af, hvordan du kvantificerer effektiviteten af ​​din kode, giver dig de værktøjer, du har brug for til at begynde at indstille den til effektivitet og afveje fordele og ulemper ved algoritmer.

10 mest almindelige programmerings- og kodningsfejl

Kodningsfejl kan føre til så mange problemer. Disse tip hjælper dig med at undgå programmeringsfejl og holde din kode meningsfuld.

Om forfatteren