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 $\mathrm{\Omega }(f(n))$‍, atunci pentru un $n$‍ suficient de mare, timpul de execuție este cel puțin $k\cdot f(n)$‍ pentru o constantă $k$‍. Iată o ilustrație pentru $\mathrm{\Omega }(f(n))$‍:

Spunem că timpul de execuție este „Ω de $f(n)$‍”. 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 $\mathrm{\Theta }(f(n))$‍ implică $O(f(n))$‍, implică totodată și $\mathrm{\Omega }(f(n))$‍. Așadar, putem spune că timpul de execuție al căutării binare în cazul cel mai nefavorabil este $\mathrm{\Omega }({\log }_{2}n)$‍.

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 $\mathrm{\Omega }(1)$‍, 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 $\mathrm{\Omega }$‍, $O$‍ și $\mathrm{\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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.