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 Θ(log2n). Nie jest jednak prawdą że czas wykonania wyszukiwania binarnego jest Θ(log2n) we wszystkich przypadkach. Na przykład, może się zdarzyć, że zgadniemy w pierwszej próbie, a wtedy czas wykonania będzie Θ(1). Cas wykonania algorytmu wyszukiwania binarnego nie jest dłuższy, niż Θ(log2n), 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(f(n)), to dla odpowiednio dużych n czas wykonania wynosi co najwyżej kf(n) dla pewnej zmiennej k. Oto jak patrzeć na czas, który jest ograniczony przez O(f(n)):
6n^2 a 100n + 300
Możemy powiedzieć, że czas wykonania wynosi "duże-O z f(n) lub po prostu "O z f(n)". 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(log2n). Możemy użyć silniejszego twierdzenia w stosunku do czasu wykonania w najgorszym przypadku, czyli: Θ(log2n). Ale w ogólnym przypadku najsilniejsze stwierdzenie, które możemy zrobić jest takie, że wyszukiwanie binarne wykonuje się w czasie O(log2n).
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 Θ(f(n)) w danej sytuacji, to ten czas jest również O(f(n)). Na przykład, jeśli najdłuższy czas wyszukiwania binarnego wynosi Θ(log2n), to oszacowanie O(log2n) 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(log2n) ale nie zawsze wykonuje się w czasie Θ(log2n).
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(n), 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(n) jest górnym ograniczeniem na czas wykonania wyszukiwania binarnego. Inne, podobnie nieprecyzyjne oszacowania mają postać O(n2), O(n3), czy O(2n). Natomiast żadne z oszacowań Θ(n), Θ(n2), Θ(n3), oraz Θ(2n) 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.