Big Omega ne spune limita inferioară a timpului de rulare al unei funcții, iar Big O ne spune limita superioară.

De multe ori, acestea sunt diferite și nu putem oferi o garanție în timpul rulării – acesta va varia între cele două limite și intrări. Dar ce se întâmplă când sunt la fel? Atunci putem da o theta (Θ) legat – funcția noastră va rula în acel timp, indiferent de ce intrare i-am da.

În general, vrem să oferim întotdeauna o legătură theta, dacă este posibil, deoarece este cea mai precisă și cea mai strânsă legătură. Dacă nu putem da o legătură theta, următorul cel mai bun lucru este cea mai strânsă legătură O posibilă.

Luați, de exemplu, o funcție care caută o matrice pentru valoarea 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. Care este cel mai bun caz? Ei bine, dacă matricea pe care i-o dăm are 0 ca primă valoare, va dura un timp constant: Ω (1)
  2. Care este cel mai rău caz? Dacă matricea nu conține 0, vom fi iterați prin întreaga matrice: O (n)

I-am dat o legătură omega și O, deci ce zici de theta? Nu-i putem da una! În funcție de matricea pe care o oferim, timpul de rulare va fi undeva între constant și liniar.

Să ne schimbăm puțin codul.

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

Vă puteți gândi la cel mai bun caz și la cel mai rău caz ?? Nu pot! Indiferent ce matrice i-am da, trebuie să parcurgem fiecare valoare din matrice. Deci funcția va dura cel puțin n timp (Ω (n)), dar știm, de asemenea, că nu va dura mai mult de n timp (O (n)). Ce inseamna asta? Funcția noastră va lua exact n timp: Θ (n).

Dacă limitele sunt confuze, gândiți-vă astfel. Avem 2 numere, x și y. Ni se dă că x <= y și că y <= x. Dacă x este mai mic sau egal cu y, iar y este mai mic sau egal cu x, atunci x trebuie să fie egal cu y!

Dacă sunteți familiarizați cu listele legate, testați-vă și gândiți-vă la duratele de rulare pentru fiecare dintre aceste funcții!

  1. obține
  2. elimina
  3. adăuga

Lucrurile devin și mai interesante atunci când consideri o listă dublă legată!

Notatie asimptotica

Cum măsurăm valoarea de performanță a algoritmilor?

Luați în considerare modul în care timpul este una dintre cele mai valoroase resurse noastre. În calcul, putem măsura performanța cu timpul necesar procesului. Dacă datele procesate de doi algoritmi sunt aceleași, putem decide cea mai bună implementare pentru a rezolva o problemă.

Facem acest lucru definind limitele matematice ale unui algoritm. Acestea sunt big-O, big-omega și big-theta, sau notațiile asimptotice ale unui algoritm. Pe un grafic, big-O ar fi cel mai lung pe care l-ar putea lua un algoritm pentru un anumit set de date sau „limita superioară”. Big-omega este ca opusul big-O, „limita inferioară”. Acolo algoritmul atinge viteza maximă pentru orice set de date. Theta mare este fie valoarea exactă a performanței algoritmului, fie o gamă utilă între limitele înguste superioare și inferioare.

Cateva exemple:

  • „Livrarea va fi acolo în timpul vieții tale.” (mare-O, limită superioară)
  • „Vă pot plăti cel puțin un dolar.” (mare-omega, limita inferioară)
  • „Maxima de azi va fi de 25 ° C, iar cea mai mică de 19 ° C.” (mare-theta, îngust)
  • “Este la un kilometru de mers pe jos până la plajă.” (mare-theta, exact)

Mai multe informatii:

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