Pojasnjena velika theta in asimptotična notacija

Big Omega nam sporoča spodnjo mejo časa izvajanja funkcije, Big O pa zgornjo mejo.

Pogosto so različni in ne moremo dati garancije za čas izvajanja - ta se bo razlikoval med obema mejama in vhodnimi podatki. Toda kaj se zgodi, ko sta enaka? Potem lahko damo vezavo theta (Θ) - naša funkcija bo delovala v tem času, ne glede na to, kakšen vložek ji damo.

Na splošno želimo vedno dati teta vezan, če je le mogoče, ker je najbolj natančen in tesno vezan. Če ne moremo določiti teta meje, je naslednja najboljša možna najtesnejša meja O.

Vzemimo na primer funkcijo, ki v matriki išče vrednost 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. Kateri je najboljši primer? No, če ima matrika, ki ji damo, prvo vrednost 0, bo trajal konstanten čas: Ω (1)
  2. Kaj je najslabši primer? Če matrika ne vsebuje 0, bomo ponovili celotno matriko: O (n)

Dali smo mu omego in O, kaj pa theta? Tega ne moremo dati! Glede na matriko, ki jo dobimo, bo čas izvajanja nekje med konstanto in linearnostjo.

Spremenimo svojo kodo nekoliko.

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

Si lahko omislite najboljši in najslabši primer ?? Ne morem! Ne glede na to, katero matriko ji damo, moramo iti skozi vsako vrednost v matriki. Torej bo funkcija trajala VSAJ n čas (Ω (n)), vemo pa tudi, da ne bo trajala dlje kot n čas (O (n)). Kaj to pomeni? Naša funkcija bo trajala natanko n časa: Θ (n).

Če so meje zmedene, pomislite na to takole. Imamo dve številki, x in y. Dobili smo, da je x <= y in da y <= x. Če je x manjši ali enak y in y manjši ali enak x, potem mora biti x enak y!

Če poznate povezane sezname, se preizkusite in razmislite o času izvajanja za vsako od teh funkcij!

  1. dobili
  2. Odstrani
  3. dodajte

Stvari postanejo še bolj zanimive, če upoštevate dvojno povezan seznam!

Asimptotski zapis

Kako izmerimo vrednost zmogljivosti algoritmov?

Razmislite, kako je čas eden izmed naših najbolj dragocenih virov. Pri računalništvu lahko merimo uspešnost s časom, potrebnim za dokončanje procesa. Če so podatki, ki jih obdelujeta dva algoritma, enaki, se lahko odločimo za najboljšo izvedbo za rešitev problema.

To naredimo tako, da določimo matematične meje algoritma. To so big-O, big-omega in big-theta ali asimptotični zapisi algoritma. Na grafu bi bil veliki O najdaljši, ki bi ga algoritem lahko uporabil za kateri koli nabor podatkov ali »zgornjo mejo«. Velika omega je kot nasprotje velikega O, "spodnja meja". Tam algoritem doseže najvišjo hitrost za kateri koli nabor podatkov. Velika teta je bodisi natančna vrednost delovanja algoritma bodisi uporaben razpon med ozkimi zgornjimi in spodnjimi mejami.

Nekaj ​​primerov:

  • "Dostava bo tam v vaši življenjski dobi." (velika-O, zgornja meja)
  • "Lahko vam plačam vsaj en dolar." (velika omega, spodnja meja)
  • "Najvišja temperatura bo danes 25 ° C, najnižja pa 19 ° C." (velik-theta, ozek)
  • "Do plaže je kilometer hoje." (big-theta, natančno)

Več informacij:

//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-predstavljajo //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/