Big Theta og asymptotisk notation forklaret

Big Omega fortæller os den nedre grænse for en funktions runtime, og Big O fortæller os den øvre grænse.

Ofte er de forskellige, og vi kan ikke garantere runtime - det vil variere mellem de to grænser og input. Men hvad sker der, når de er de samme? Så kan vi give en theta (Θ) bundet - vores funktion vil køre på det tidspunkt, uanset hvilket input vi giver det.

Generelt ønsker vi altid at give en theta-bånd, hvis det er muligt, fordi det er den mest nøjagtige og strammeste bundet. Hvis vi ikke kan give en theta-bund, er den næstbedste ting den strammeste O-bund, der er mulig.

Tag for eksempel en funktion, der søger i en matrix efter værdien 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. Hvad er det bedste tilfælde? Nå, hvis det array, vi giver det, har 0 som den første værdi, tager det konstant tid: Ω (1)
  2. Hvad er det værste tilfælde? Hvis matrixen ikke indeholder 0, vil vi have itereret gennem hele arrayet: O (n)

Vi har givet den en omega og O-bundet, så hvad med theta? Vi kan ikke give det en! Afhængigt af det array, vi giver det, vil køretiden være et sted imellem konstant og lineær.

Lad os ændre vores kode lidt.

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

Kan du tænke på en best case og worst case ?? Jeg kan ikke! Uanset hvilket array vi giver det, skal vi gentage alle værdier i arrayet. Så funktionen tager MINDST n tid (Ω (n)), men vi ved også, at den ikke tager længere tid end n tid (O (n)). Hvad betyder det? Vores funktion tager nøjagtigt n tid: Θ (n).

Hvis grænserne er forvirrende, så tænk over det sådan. Vi har 2 tal, x og y. Vi får at x <= y og at y <= x. Hvis x er mindre end eller lig med y, og y er mindre end eller lig med x, så skal x være lig med y!

Hvis du er fortrolig med sammenkædede lister, kan du teste dig selv og tænke over driftstiderne for hver af disse funktioner!

  1. fjerne
  2. tilføje

Ting bliver endnu mere interessante, når du overvejer en dobbeltkoblet liste!

Asymptotisk notation

Hvordan måler vi præstationsværdien af ​​algoritmer?

Overvej hvordan tid er en af ​​vores mest værdifulde ressourcer. I computing kan vi måle ydeevne med den tid, det tager en proces at gennemføre. Hvis dataene, der behandles af to algoritmer, er de samme, kan vi beslutte den bedste implementering for at løse et problem.

Vi gør dette ved at definere de matematiske grænser for en algoritme. Disse er big-O, big-omega og big-theta eller de asymptotiske notationer af en algoritme. På en graf ville big-O være den længste, en algoritme kunne tage for et givet datasæt eller den "øvre grænse". Big-omega er som det modsatte af big-O, den "nedre grænse". Det er her, algoritmen når sin højeste hastighed for ethvert datasæt. Stor theta er enten algoritmens nøjagtige ydeevne eller et nyttigt interval mellem smalle øvre og nedre grænser.

Nogle eksempler:

  • "Leveringen vil være der inden for din levetid." (stor-O, øvre grænse)
  • "Jeg kan betale dig mindst en dollar." (stor-omega, nedre grænse)
  • "Den høje i dag vil være 25 ° C og den lave vil være 19 ° C." (stor-theta, smal)
  • "Det er en kilometer gåtur til stranden." (stor-theta, nøjagtig)

Mere information:

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