Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 3: Asymptotyczne tempo wzrostuNotacja 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, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, to dla odpowiednio dużych n czas wykonania wynosi co najmniej k, dot, f, left parenthesis, n, right parenthesis dla pewnej stałej k. Poniższy obrazek pokazuje jak można myśleć o czasie wykonania rzędu \Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:
Mówimy, że czas wykonania wynosi "duże-Ω funkcji 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, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis automatycznie wynika oszacowanie O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, automatycznie wynika także oszacowanie \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, 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, 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, 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-O, 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.
Chcesz dołączyć do dyskusji?
- Skoro jest to ograniczenie dolne to nie powinno być " W najlepszym przypadku" zamiast "w najgorszym wypadku"?(4 głosy)