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 Ω(f(n)) \Omega(f(n)) , to dla odpowiednio dużych n n czas wykonania wynosi co najmniej kf(n) k \cdot f(n) dla pewnej stałej k k . Poniższy obrazek pokazuje jak można myśleć o czasie wykonania rzędu Ω(f(n)) \Omega(f(n)) :
Mówimy, że czas wykonania wynosi "duże-Ω funkcji f(n) 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 Θ(f(n)) \Theta(f(n)) automatycznie wynika oszacowanie O(f(n)) O(f(n)) , automatycznie wynika także oszacowanie Ω(f(n)) \Omega(f(n)) . Możemy więc powiedzieć, że złożoność obliczeniowa przeszukiwania binarnego w najgorszym przypadku wynosi Ω(log2n) \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 Ω(1) \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 nn, 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, duże-OO, oraz duże-Θ\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.
Ładowanie