Izskaidrots lielais teta un asimptotiskais apzīmējums

Lielā Omega mums paskaidro funkcijas izpildes laika apakšējo robežu, bet Lielā O - augšējo robežu.

Bieži vien tie ir atšķirīgi, un mēs nevaram garantēt izpildlaiku - tas mainīsies starp abām robežām un ieejām. Bet kas notiek, kad viņi ir vienādi? Tad mēs varam dot saistītu teta (Θ) - mūsu funkcija darbosies šajā laikā neatkarīgi no tā, kādu ieguldījumu mēs to ievadīsim.

Kopumā mēs vienmēr vēlamies piešķirt saistītu teta, ja iespējams, jo tā ir visprecīzākā un stingrākā saite. Ja mēs nevaram dot saistītu teta, nākamais labākais ir iespējami stingrākais O saistījums.

Veikt, piemēram, funkciju, kas masīvā meklē vērtību 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. Kāds ir labākais gadījums? Nu, ja masīvam, kuru mēs tam piešķiram, kā pirmā vērtība ir 0, tas prasīs nemainīgu laiku: Ω (1)
  2. Kas ir sliktākais gadījums? Ja masīvā nav 0, mēs atkārtosimies caur visu masīvu: O (n)

Mēs tam esam piešķīruši saistītu omega un O, un kā tad ar tetu? Mēs to nevaram dot! Atkarībā no tā, kādu masīvu mēs tam piešķiram, izpildlaiks būs kaut kur starp konstanti un lineāri.

Nedaudz mainīsim kodu.

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

Vai jūs varat iedomāties labāko un sliktāko gadījumu ?? Es nevaru! Neatkarīgi no tā, kādu masīvu mēs tam piešķiram, mums ir jāatkārto katra masīva vērtība. Tātad funkcija prasīs VISMAZ n laiku (Ω (n)), bet mēs arī zinām, ka tas neaizņems ilgāk par n laiku (O (n)). Ko tas nozīmē? Mūsu funkcija aizņems tieši n laiku: Θ (n).

Ja robežas ir neskaidras, padomājiet par to šādi. Mums ir 2 cipari, x un y. Mums ir dots, ka x <= y un ka y <= x. Ja x ir mazāks vai vienāds ar y, un y ir mazāks vai vienāds ar x, tad x ir vienāds ar y!

Ja esat iepazinies ar saistītajiem sarakstiem, pārbaudiet sevi un padomājiet par katras šīs funkcijas izpildlaiku!

  1. gūt
  2. noņemt
  3. pievienot

Lietas kļūst vēl interesantākas, ja ņemat vērā divkārši saistīto sarakstu!

Asimptotiskais apzīmējums

Kā mēs izmērām algoritmu veiktspējas vērtību?

Apsveriet, kā laiks ir viens no mūsu vērtīgākajiem resursiem. Aprēķinot, mēs varam novērtēt veiktspēju ar laiku, kas vajadzīgs procesa pabeigšanai. Ja divu algoritmu apstrādātie dati ir vienādi, mēs varam izlemt par labāko risinājumu problēmas risināšanai.

Mēs to darām, definējot algoritma matemātiskās robežas. Tie ir big-O, big-omega un big-theta vai algoritma asimptotiskie apzīmējumi. Grafikā lielais O būtu garākais, kādu algoritms varētu veikt jebkurai konkrētai datu kopai, vai “augšējā robeža”. Lielā omega ir kā pretstats lielajam O, “apakšējā robeža”. Tieši tur algoritms sasniedz maksimālo ātrumu jebkurai datu kopai. Lielā teta ir vai nu precīza algoritma veiktspējas vērtība, vai arī noderīgs diapazons starp šauru augšējo un apakšējo robežu.

Daži piemēri:

  • "Piegāde būs jūsu dzīves laikā." (liels-O, augšējais ierobežojums)
  • "Es varu jums samaksāt vismaz vienu dolāru." (lielā omega, apakšējā robeža)
  • "Šodien augstākā temperatūra būs 25ºC, bet zemā - 19ºC." (lielā teta, šaurs)
  • "Līdz pludmalei ir kilometra gājiens." (lielā teta, precīza)

Vairāk informācijas:

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