Notacja duże Ω (duże-Omega)

Czasem chcemy powiedzieć, że algorytm zajmuje przynajmniej pewną ilość czasu bez podawania górnej granicy. Używamy notacji duże-Ω (jest to grecka litera "omega").

Jeśli czas wykonania ogranicza $\mathrm{\Omega }(f(n))$‍, to dla odpowiednio dużych $n$‍ czas wykonania wynosi co najmniej $k\cdot f(n)$‍ dla pewnej stałej $k$‍. Poniższy obrazek pokazuje jak można myśleć o czasie wykonania rzędu $\mathrm{\Omega }(f(n))$‍:

Mówimy, że czas wykonania wynosi "duże-Ω funkcji $f(n)$‍." Używamy notacji duże-Ω dla oznaczenia asymptotycznej granicy dolnej ponieważ ogranicza wzrost czasu wykonania od dołu dla odpowiedno dużych wartości podanych na wejściu.

Dokładnie na tej samej zasadzie, jak z oszacowania $\mathrm{\Theta }(f(n))$‍ automatycznie wynika oszacowanie $O(f(n))$‍, automatycznie wynika także oszacowanie $\mathrm{\Omega }(f(n))$‍. Możemy więc powiedzieć, że złożoność obliczeniowa przeszukiwania binarnego w najgorszym przypadku wynosi $\mathrm{\Omega }({\log }_{2}n)$‍.

Możemy również dokonać poprawnych (lecz nieprecyzyjnych) stwierdzeń używając notacji duże-Ω. Na przykład, gdybyś miał milion złotych w kieszeni, mógłbyś stwierdzić "Mam pewną ilość pieniędzy w kieszeni i jest to co najmniej 10 złotych". Stwierdzenie prawdziwe, ale w oczywisty sposób niezbyt dokładne. Możesz również powiedzieć, że czas wykonania w najgorszym przypadku jest $\mathrm{\Omega }(1)$‍, ponieważ algorytm zawsze zajmie przynajmniej stałą ilość czasu czas.

Oczywiście, kiedy mamy do czynienia z logarytmiczną zależnością złożoności obliczeniowej od $n$‍, staramy się określić czas wykonania jak najbardziej dokładnie. Przeanalizujemy teraz kilka przykładów, co powinno pomóc Ci zrozumieć notację duże-$\mathrm{\Omega }$‍, duże-$O$‍, oraz duże-$\mathrm{\Theta }$‍.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.