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 $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, to dla odpowiednio dużych $n$n czas wykonania wynosi co najmniej $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis dla pewnej stałej $k$k. Poniższy obrazek pokazuje jak można myśleć o czasie wykonania rzędu $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:

Mówimy, że czas wykonania wynosi "duże-Ω funkcji $f(n)$f, left parenthesis, n, right parenthesis." 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 $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis automatycznie wynika oszacowanie $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, automatycznie wynika także oszacowanie $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Możemy więc powiedzieć, że złożoność obliczeniowa przeszukiwania binarnego w najgorszym przypadku wynosi $\Omega(\log_2 n)$\Omega, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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 $\Omega(1)$\Omega, left parenthesis, 1, right parenthesis, 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$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-$\Omega$\Omega, duże-$O$O, oraz duże-$\Theta$\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.