Hva er Big-O Notation?

Har du noen gang lurt på hvorfor et program du skrev tok så lang tid å kjøre? Kanskje du vil vite om du kan gjøre koden mer effektiv. Å forstå hvordan koden kjører, kan bringe koden din til neste nivå. Big-O-notasjon er et praktisk verktøy for å beregne hvor effektiv koden din egentlig er.

Hva er Big-O-notasjon?

Big-O-notasjon gir deg en måte å beregne hvor lang tid det vil ta å kjøre koden din. Du kan fysisk tid hvor lang tid det tar for koden din å kjøre, men med den metoden er det vanskelig å fange små tidsforskjeller. For eksempel er tiden det går mellom å kjøre 20 og 50 kodelinjer veldig liten. Imidlertid, i et stort program, kan disse ineffektivitetene legge seg opp.

Big-O-notasjon teller hvor mange trinn en algoritme må utføre for å måle effektiviteten. Å nærme seg koden din på denne måten kan være veldig effektiv hvis du trenger å stille inn koden din for å øke effektiviteten. Big-O-notasjon vil gjøre det mulig å måle forskjellige algoritmer etter antall trinn det krever for å kjøre og objektivt sammenligne algoritmenes effektivitet.

Hvordan beregner du Big-O-notasjon

La oss vurdere to funksjoner som teller hvor mange individuelle sokker som er i en skuff. Hver funksjon tar antall par sokker og returnerer antall individuelle sokker. Koden er skrevet i Python, men det påvirker ikke hvordan vi vil telle antall trinn.

Algoritme 1:

def sockCounter (numberOfPairs):
individualSocks = 0
for x innen rekkevidde (numberOfPairs):
individualSocks = individualSocks + 2
returner individualSocks

Algoritme 2:

def sockCounter (numberOfPairs):
returnummerOfPairs * 2

Dette er et dumt eksempel, og du bør kunne fortelle hvilken algoritme som er mer effektiv. Men for praksis, la oss løpe gjennom hver.

I SLEKT: Hva er en funksjon i programmering?

Hva er en funksjon i programmering?

Hvis du lærer å programmere din egen kode, må du forstå hva funksjonene er.

Algoritme 1 har mange trinn:

1. Den tilordner en verdi på null til variabelen individualSocks.
2. Den tilordner en verdi på en til variabelen i.
3. Den sammenligner verdien av i med numberOfPairs.
4. Det legger to til individualSocks.
5. Det tilordner den økte verdien av individualSocks til seg selv.
6. Det øker jeg en etter en.
7. Den går deretter tilbake gjennom trinn 3 til 6 for samme antall ganger som (indiviualSocks - 1).

Antall trinn vi må fullføre for algoritme en kan uttrykkes som:

4n + 2

Det er fire trinn som vi må fullføre n ganger. I dette tilfellet vil n være lik verdien av numberOfPairs. Det er også to trinn som er fullført en gang.

Til sammenligning har algoritme 2 bare ett trinn. Verdien på numberOfPairs multipliseres med to. Vi vil uttrykke det som:

1

Hvis det ikke allerede var tydelig, kan vi nå enkelt se at algoritme 2 er mer effektiv ganske mye.

Big-O-analyse

Generelt, når du er interessert i Big-O-notasjonen av en algoritme, er du mer interessert i den totale effektiviteten og mindre så i finkorneanalysen av antall trinn. For å forenkle notasjonen kan vi bare oppgi størrelsen på effektiviteten.

I eksemplene ovenfor vil algoritme 2 uttrykkes som en:

O (1)

Men algoritme 1 vil forenkles som:

På)

Dette raske øyeblikksbildet forteller oss hvordan effektiviteten til algoritmen en er knyttet til verdien av n. Jo større antall, jo flere trinn må algoritmen fullføre.

Lineær kode

Fordi vi ikke vet verdien av n, er det mer nyttig å tenke på hvordan verdien av n påvirker mengden kode som trenger å kjøre. I algoritme 1 kan vi si at forholdet er lineært. Hvis du plotter antall trinn vs. verdien av n får du en rett linje som går opp.

Kvadratisk kode

Ikke alle relasjoner er så enkle som det lineære eksemplet. Tenk deg at du har en 2D-matrise, og at du vil søke etter en verdi i matrisen. Du kan opprette en algoritme som denne:

def searchForValue (targetValue, arraySearched):
foundTarget = Usann
for x i matrix
for y i x:
hvis (y == targetValue):
foundTarget = Sant
retur funnet mål

I dette eksemplet avhenger antall trinn av antall matriser i arraySearched og antall verdier i hver array. Så det forenklede antall trinn vil være n * n eller n².

Dette forholdet er et kvadratisk forhold, noe som betyr at antall trinn i algoritmen vår vokser eksponentielt med n. I Big-O-notasjonen vil du skrive det som:

O (n²)

I SLEKT: Nyttige verktøy for å sjekke, rense og optimalisere CSS-filer

Logaritmisk kode

Selv om det er mange andre forhold, er det siste forholdet vi vil se på logaritmiske forhold. For å oppdatere minnet ditt, er loggen til et nummer eksponentverdien som kreves for å nå et tall gitt en base. For eksempel:

logg 2 (8) = 3

Loggen er lik tre fordi hvis basen vår var 2, ville vi trenge en eksponentverdi på 3 for å komme til tallet 8.

Så forholdet til en logaritmisk funksjon er det motsatte av et eksponentielt forhold. Når n øker, kreves det færre nye trinn for å kjøre algoritmen.

Ved første øyekast virker dette kontraintuitivt. Hvordan kan trinnene til en algoritme vokse langsommere enn n? Et godt eksempel på dette er binære søk. La oss vurdere en algoritme for å søke etter et tall i en rekke unike verdier.

• Vi starter med en matrise for å søke i rekkefølgen fra minste til største.
• Deretter vil vi sjekke verdien midt i matrisen.
• Hvis tallet ditt er høyere, vil vi ekskludere de lavere tallene i søket vårt, og hvis tallet var lavere, vil vi ekskludere de høyere tallene.
• Nå skal vi se på det midterste tallet på de gjenværende tallene.
• Igjen vil vi ekskludere halvparten av tallene basert på om målverdien vår er høyere eller lavere enn middelverdien.
• Vi vil fortsette denne prosessen til vi finner målet vårt, eller bestemme at det ikke er i listen.

Som du kan se, siden binære søk eliminerer halvparten av de mulige verdiene hvert pass, etter hvert som n blir større, påvirkes effekten knapt så mange ganger vi sjekker matrisen. For å uttrykke dette i Big-O-notasjon, vil vi skrive:

O (logg (n))

Viktigheten av Big-O Notation

Big-O-nasjonen gir deg en rask og enkel måte å kommunisere hvor effektiv en algoritme er. Dette gjør det lettere å bestemme mellom forskjellige algoritmer. Dette kan være spesielt nyttig hvis du bruker en algoritme fra et bibliotek og ikke nødvendigvis vet hvordan koden ser ut.

Når du først lærer å kode, begynner du med lineære funksjoner. Som du kan se fra grafen ovenfor, vil det komme deg veldig langt. Men når du blir mer erfaren og begynner å bygge mer kompleks kode, begynner effektivitet å bli et problem. En forståelse av hvordan du kan kvantifisere effektiviteten til koden din, vil gi deg verktøyene du trenger for å begynne å innstille den for effektivitet og veie fordeler og ulemper med algoritmer.

10 vanligste programmerings- og kodingsfeil

Kodningsfeil kan føre til så mange problemer. Disse tipsene vil hjelpe deg med å unngå programmeringsfeil og holde koden din meningsfull.

Om forfatteren