If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Notacja duże-O

Notacji duże-Θ używamy do ograniczenia asymptotycznego tempa wzrostu czasu wykonania algorytmu od góry i od dołu, za pomocą dwóch stałych współczynników. Czasem jednak zdarza się, że chcemy ograniczyć czas wykonania tylko od góry.
Na przykład, w przypadku wyszukiwania binarnego, w najgorszym przypadku czas obliczeń wynosi \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. Nie jest jednak prawdą że czas wykonania wyszukiwania binarnego jest \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis we wszystkich przypadkach. Na przykład, może się zdarzyć, że zgadniemy w pierwszej próbie, a wtedy czas wykonania będzie \Theta, left parenthesis, 1, right parenthesis. Cas wykonania algorytmu wyszukiwania binarnego nie jest dłuższy, niż \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, ale czasem może być krótszy.
Było by wygodnie posiadać notację asymptotyczną, w której można byłoby wyrazić zdanie "Czas rośnie nie szybciej niż tak, lecz może rosnąć wolniej". Notacji "duże-O" używamy właśnie w takich przypadkach.
Jeśli czas wykonania jest ograniczony przez O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, to dla odpowiednio dużych n czas wykonania wynosi co najwyżej k, dot, f, left parenthesis, n, right parenthesis dla pewnej zmiennej k. Oto jak patrzeć na czas, który jest ograniczony przez O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:
6n^2 a 100n + 300
Możemy powiedzieć, że czas wykonania wynosi "duże-O z f, left parenthesis, n, right parenthesis lub po prostu "O z f, left parenthesis, n, right parenthesis". Notacji duże-O używamy w celu wyznaczenia górnych granic asymptotycznych, ponieważ ogranicza ona wzrost czasu wykonania dla dużych danych wejściowych.
Obecnie mamy możliwość scharakteryzowania czasu wyszukiwania binarnego we wszystkich przypadkach. Możemy powiedzieć, że czas w wyszukiwaniu binarnym jest zawsze O, left parenthesis, log, start base, 2, end base, n, right parenthesis. Możemy użyć silniejszego twierdzenia w stosunku do czasu wykonania w najgorszym przypadku, czyli: \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. Ale w ogólnym przypadku najsilniejsze stwierdzenie, które możemy zrobić jest takie, że wyszukiwanie binarne wykonuje się w czasie O, left parenthesis, log, start base, 2, end base, n, right parenthesis.
Jeśli wrócisz do definicji notacji duże-Θ to zauważysz, że jest bardzo zbliżona do notacji duże-O, z wyjątkiem tego że, notacja duże-Θ organiczna czas z dwóch stron, a nie tylko z góry. Jeśli mówimy, że czas wykonania wynosi \Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis w danej sytuacji, to ten czas jest również O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Na przykład, jeśli najdłuższy czas wyszukiwania binarnego wynosi \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, to oszacowanie O, left parenthesis, log, start base, 2, end base, n, right parenthesis jest także prawdziwe.
Twierdzenie odwrotne nie musi być prawdziwe: jak widzieliśmy, można powiedzieć, że wyszukiwanie binarne zawsze wykonuje się w czasie O, left parenthesis, log, start base, 2, end base, n, right parenthesis ale nie zawsze wykonuje się w czasie \Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis.
Notacja duże-O opisuje asymptotyczne ograniczenie od góry, a nie koniecznie ograniczenie, które jest asymptotycznie ścisłe, za pomocą notacji duże-O możemy sformułować stwierdzenia, które wyglądają na fałszywe, choć są technicznie jak najbardziej prawdziwe. Na przykład, stwierdzenie że czas wyszukiwania binarnego jest rzędu O, left parenthesis, n, right parenthesis, jest jak najbardziej słuszne, dlatego że czas wykonania tego algorytmu rośnie nie szybciej niż pewna stała razy n. W rzeczywistości jednak, rośnie znacznie wolniej.
Pomyśl o tym w taki sposób, Powiedzmy, że masz w kieszeni 10 złotych. Idziesz do swojego znajomego i mówisz mu: "mam pewną kwotę pieniędzy w kieszeni i jestem pewien, że jest to nie więcej niż jeden milion złotych." Twoje stwierdzenie jest prawdą, ale nie jest bardzo precyzyjne.
Milion złotych to bez wątpienia ograniczenie z góry w stosunku do 10 złotych, tak samo jak O, left parenthesis, n, right parenthesis jest górnym ograniczeniem na czas wykonania wyszukiwania binarnego. Inne, podobnie nieprecyzyjne oszacowania mają postać O, left parenthesis, n, squared, right parenthesis, O, left parenthesis, n, cubed, right parenthesis, czy O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. Natomiast żadne z oszacowań \Theta, left parenthesis, n, right parenthesis, \Theta, left parenthesis, n, squared, right parenthesis, \Theta, left parenthesis, n, cubed, right parenthesis, oraz \Theta, left parenthesis, 2, start superscript, n, end superscript, right parenthesis byłyby prawidłowe w stosunku do opisu czasu wykonania algorytmu wyszukiwania binarnego w jakimkolwiek przypadku.

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?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.