Hva er Big-O Notation?

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 kodekjøringer 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 Notation?

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



hvordan sette en gif som bakgrunn

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





Hvordan beregner du Big-O Notation

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 in range(numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

Algoritme 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

Dette er et dumt eksempel, og du bør enkelt kunne fortelle hvilken algoritme som er mer effektiv. Men for trening, la oss gå gjennom hver.



I SLEKT: Hva er en funksjon i programmering?

Algoritme 1 har mange trinn:



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

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

4n + 2

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

Til sammenligning har algoritme 2 bare ett trinn. Verdien av numberOfPairs ganges med to. Vi vil uttrykke det som:

1

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

Big-O-analyse

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

I eksemplene ovenfor vil algoritme 2 bli uttrykt som en:

O(1)

Men algoritme 1 vil bli forenklet som:

O(n)

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

Lineær kode

Bildekreditt: Nick Fledderus/ Substantivprosjekt

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

Kvadratisk kode

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

def searchForValue(targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
for y in x:
if(y == targetValue):
foundTarget = True
return foundTarget

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

beste gratis live tv -app for android

Bildekreditt: Nick Fledderus/ Substantivprosjekt

Dette forholdet er et kvadratisk forhold, noe som betyr at antall trinn i algoritmen vår vokser eksponentielt med n. I Big-O-notasjon 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 for et tall eksponentverdien som kreves for å nå et tall gitt en base. For eksempel:

log 2 (8) = 3

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

Bildekreditt: Nick Fledderus/ Substantivprosjekt

Så forholdet til en logaritmisk funksjon er det motsatte av et eksponensielt forhold. Når n øker, kreves 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 som er i rekkefølge fra den minste til den største.
  • Deretter sjekker vi verdien i midten av 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å midten av de gjenværende tallene.
  • Igjen vil vi ekskludere halvparten av tallene basert på om vår målverdi er høyere eller lavere enn mellomverdien.
  • Vi vil fortsette denne prosessen til vi finner målet vårt, eller fastslår at det ikke er på listen.

Som du kan se, siden binære søk eliminerer halvparten av de mulige verdiene for hver passering, ettersom n blir større, påvirkes effekten på antall ganger vi sjekker matrisen knapt. For å uttrykke dette i Big-O-notasjon, ville vi skrive:

O(log(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.

"Ingen internett, sikret"

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

Dele Dele kvitring E -post 10 mest vanlige programmerings- og kodingsfeil

Kodingsfeil kan føre til så mange problemer. Disse tipsene hjelper deg med å unngå programmeringsfeil og holder koden din meningsfylt.

Les neste Relaterte temaer
  • Programmering
  • Programmering
Om forfatteren Jennifer Seaton(21 artikler publisert)

J. Seaton er en vitenskapsforfatter som spesialiserer seg på å bryte ned komplekse temaer. Hun har en doktorgrad fra University of Saskatchewan; forskningen hennes fokuserte på å utnytte spillbasert læring for å øke studentengasjementet online. Når hun ikke jobber, vil du finne henne mens hun leser, spiller videospill eller hagearbeid.

Mer fra Jennifer Seaton

Abonner på vårt nyhetsbrev

Bli med i vårt nyhetsbrev for tekniske tips, anmeldelser, gratis ebøker og eksklusive tilbud!

Klikk her for å abonnere