Big Theta og Asymptotic Notation Explained

Big Omega forteller oss den nedre grensen for funksjonstiden, og Big O forteller den øvre grensen.

Ofte er de forskjellige, og vi kan ikke garantere kjøretiden - den vil variere mellom de to grensene og inngangene. Men hva skjer når de er de samme? Da kan vi gi en theta (Θ) bundet - funksjonen vår vil løpe på den tiden, uansett hvilken inngang vi gir den.

Generelt sett ønsker vi alltid å gi en theta-binding hvis mulig fordi den er den mest nøyaktige og tetteste. Hvis vi ikke kan gi et theta-bånd, er det nest beste tettest mulig O-bundet.

Ta for eksempel en funksjon som søker i en matrise etter verdien 0:

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false
  1. Hva er den beste saken? Vel, hvis matrisen vi gir den har 0 som den første verdien, vil det ta konstant tid: Ω (1)
  2. Hva er det verste tilfellet? Hvis matrisen ikke inneholder 0, vil vi ha iterert gjennom hele matrisen: O (n)

Vi har gitt den en omega og O-bundet, så hva med theta? Vi kan ikke gi den en! Avhengig av matrisen vi gir den, vil kjøretiden være et sted mellom konstant og lineær.

La oss endre koden vår litt.

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

Kan du tenke deg en best case og worst case ?? Jeg kan ikke! Uansett hvilken matrise vi gir den, må vi gjenta gjennom hver verdi i matrisen. Så funksjonen vil ta MINST n tid (Ω (n)), men vi vet også at den ikke vil ta lenger tid enn n tid (O (n)). Hva betyr dette? Vår funksjon vil ta nøyaktig n tid: Θ (n).

Hvis grensene er forvirrende, tenk på det slik. Vi har to tall, x og y. Vi får at x <= y og at y <= x. Hvis x er mindre enn eller lik y, og y er mindre enn eller lik x, så må x være lik y!

Hvis du er kjent med koblede lister, kan du teste deg selv og tenke på kjøretidene for hver av disse funksjonene!

  1. fjerne
  2. legge til

Ting blir enda mer interessante når du vurderer en dobbeltkoblet liste!

Asymptotisk notasjon

Hvordan måler vi ytelsesverdien til algoritmer?

Tenk på hvordan tid er en av våre mest verdifulle ressurser. I databehandling kan vi måle ytelse med hvor lang tid det tar å fullføre prosessen. Hvis dataene som er behandlet av to algoritmer er de samme, kan vi bestemme den beste implementeringen for å løse et problem.

Vi gjør dette ved å definere de matematiske grensene til en algoritme. Dette er big-O, big-omega og big-theta, eller de asymptotiske notasjonene til en algoritme. På en graf ville big-O være den lengste en algoritme kunne ta for et gitt datasett, eller "øvre grense". Big-omega er som det motsatte av big-O, den "nedre grensen". Det er der algoritmen når topphastigheten for ethvert datasett. Stor teta er enten den nøyaktige ytelsesverdien til algoritmen, eller et nyttig område mellom smale øvre og nedre grenser.

Noen eksempler:

  • "Leveransen vil være der i løpet av livet ditt." (stor-O, øvre grense)
  • "Jeg kan betale deg minst en dollar." (stor-omega, nedre grense)
  • "Den høye i dag vil være 25 ° C og den lave vil være 19 ° C." (stor-theta, smal)
  • "Det er en kilometer spasertur til stranden." (stor-theta, eksakt)

Mer informasjon:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notasjon-representerer //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/