Notația Marele-O

Folosim notația Θ pentru a încadra asimptotic creșterea unui timp de execuție între doi termeni constanți, unul mai mare și unul mai mic. Însă, uneori dorim să aflăm doar limita superioară a timpului de execuție.

De exemplu, deși timpul de execuție în cazul cel mai nefavorabil al căutării binare este $\mathrm{\Theta }({\log }_{2}n)$‍, ar fi greșit să spunem că în toate cazurile căutarea binară se execută în $\mathrm{\Theta }({\log }_{2}n)$‍. Ce se întâmplă atunci când găsim valoarea căutată chiar din primele încercări? Atunci algoritmul se execută în $\mathrm{\Theta }(1)$‍ timp. Timpul de execuție al căutării binare nu este niciodată mai mare decât $\mathrm{\Theta }({\log }_{2}n)$‍, dar poate fi mai mic.

Ar fi convenabil să existe o notație asimptotică ce are înțelesul „timpul de execuție crește cel mult atât, dar poate crește și mai puțin”.

Dacă un timp de execuție este $O(f(n))$‍, atunci pentru un $n$‍ suficient de mare, timpul de execuție este cel mult $k\cdot f(n)$‍ pentru o constantă $k$‍. Iată o iulstrație pentru $O(f(n))$‍:

Spunem că timpul de execuție este „O de $f(n)$‍”. Folosim notația O pentru limite asimptotice superioare, deoarece aceasta limitează superior creșterea timpului de execuție pentru dimensiuni ale datelor de intrare suficient de mari.

Acum avem un mod de a caracteriza timpul de execuție al căutării binare pentru toate cazurile. Putem spune că timpul de execuție al căutării binare este întotdeauna $O({\log }_{2}n)$‍. Putem face o afirmație mai concretă despre timpul de execuție în cazul cel mai nefavorabil: este egal cu $\mathrm{\Theta }({\log }_{2}n)$‍. Însă, o afirmație generală care include toate cazurile este că timpul de execuție al căutării binare este $O({\log }_{2}n)$‍.

Dacă recitești definiția notației Θ, vei observa ca e asemănătoare cu notația O, cu excepția faptului că Θ limitează superior și inferior timpul de execuție, nu doar superior. Dacă spunem că un timp de execuție este egal cu $\mathrm{\Theta }(f(n))$‍ într-un caz, atunci este și egal cu $O(f(n))$‍. De exemplu, putem spune că din cauza faptului că timpul de execuție în cazul cel mai nefavorabil al căutării binare este $\mathrm{\Theta }({\log }_{2}n)$‍, este și $O({\log }_{2}n)$‍.

Reciproc nu este adevărat tot timpul: după cum am văzut, putem spune despre căutarea binară că se execută întotdeauna într-un timp $O({\log }_{2}n)$‍, dar nu putem spune că se execută întotdeauna în $\mathrm{\Theta }({\log }_{2}n)$‍.

Deoarece notația O oferă doar o limită asimptotică superioară, și nu neapărat una foarte strânsă, putem face afirmații care par incorecte la prima vedere, dar sunt corecte din punct de vedere tehnic. De exemplu, este corect să spunem despre căutarea binară că se execută în $O(n)$‍, pentru că timpul său de execuție crește mai lent decât o constantă înmulțită cu $n$‍.

Gândește-te altfel la această idee. Să presupunem că ai 10 lei în buzunar și îi spui unui prieten: „Am o sumă de bani în buzunar și îți garantez că este mai mică decât un milion de lei”. Afirmația ta este complet adevărată, însă nu este extrem de precisă.

Un milion de lei este o limită superioară pentru 10 lei, așa cum $O(n)$‍ este o limită superioară a timpului de execuție al căutării binare. Alte limite superioare imprecise ale căutării binare ar fi $O(n^2)$‍, $O(n^3)$‍ și $O(2^n)$‍. Însă nicio valoare din șirul $\mathrm{\Theta }(n)$‍, $\mathrm{\Theta }(n^2)$‍, $\mathrm{\Theta }(n^3)$‍ și $\mathrm{\Theta }(2^n)$‍ nu descrie corect timpul de execuție al căutării binare pentru niciun caz.

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.