Notația Marele-Ω (Marele-Omega)

Uneori dorim să spunem că un algoritm se execută în cel puțin un anumit interval de timp, fără a menționa o limită superioară. Folosim notația Ω (litera grecească omega).

Dacă un timp de execuție este $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, atunci pentru un $n$n suficient de mare, timpul de execuție este cel puțin $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis pentru o constantă $k$k. Iată o ilustrație pentru $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:

Spunem că timpul de execuție este „Ω de $f(n)$f, left parenthesis, n, right parenthesis”. Folosim notația Ω pentru limite asimptotice inferioare, deoarece aceasta limitează inferior creșterea timpului de execuție pentru dimensiuni ale datelor de intrare suficient de mari.

Așa cum $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis implică $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, implică totodată și $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Așadar, putem spune că timpul de execuție al căutării binare în cazul cel mai nefavorabil este $\Omega(\log_2 n)$\Omega, left parenthesis, log, start base, 2, end base, n, right parenthesis.

De asemenea, putem face afirmații corecte, dar imprecise folosind notația Ω. De exemplu, dacă ai chiar un milion de lei în buzunar, poți spune: „Am o sumă de bani în buzunar și este cel puțin 10 lei”. Afirmația este corectă, dar nu e foarte precisă. Similar, putem spune, corect dar imprecis, că timpul de execuție al căutării binare în cazul cel mai nefavorabil este $\Omega(1)$\Omega, left parenthesis, 1, right parenthesis, deoarece știm că se execută într-un timp cel puțin constant.

În mod normal, atunci când vorbim despre algoritmi, încercăm să le descriem timpul de execuție cât mai exact posibil. Exemplele de afirmații imprecise pe care le-am dat au scopul să te ajute să înțelegi mai bine notațiile $\Omega$\Omega, $O$O și $\Theta$\Theta.

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.