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 $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, ar fi greșit să spunem că în toate cazurile căutarea binară se execută în $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. Ce se întâmplă atunci când găsim valoarea căutată chiar din primele încercări? Atunci algoritmul se execută în $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis timp. Timpul de execuție al căutării binare nu este niciodată mai mare decât $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, 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))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, atunci pentru un $n$n suficient de mare, timpul de execuție este cel mult $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis pentru o constantă $k$k. Iată o iulstrație pentru $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:

Spunem că timpul de execuție este „O de $f(n)$f, left parenthesis, n, right parenthesis”. 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)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis. Putem face o afirmație mai concretă despre timpul de execuție în cazul cel mai nefavorabil: este egal cu $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. Î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)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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 $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis într-un caz, atunci este și egal cu $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. De exemplu, putem spune că din cauza faptului că timpul de execuție în cazul cel mai nefavorabil al căutării binare este $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, este și $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis, dar nu putem spune că se execută întotdeauna în $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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)$O, left parenthesis, n, right parenthesis, pentru că timpul său de execuție crește mai lent decât o constantă înmulțită cu $n$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)$O, left parenthesis, n, right parenthesis 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, left parenthesis, n, squared, right parenthesis, $O(n^3)$O, left parenthesis, n, cubed, right parenthesis și $O(2^n)$O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. Însă nicio valoare din șirul $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis, $\Theta(n^3)$\Theta, left parenthesis, n, cubed, right parenthesis și $\Theta(2^n)$\Theta, left parenthesis, 2, start superscript, n, end superscript, right parenthesis 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ă a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.