Jeśli widzisz tę wiadomość oznacza to, że mamy problemy z załadowaniem zewnętrznych materiałów na naszej stronie internetowej.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Główna zawartość

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

Chcesz dołączyć do dyskusji?

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.