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 $\mathrm{\Theta }({\log }_{2}n)$‍. Nie jest jednak prawdą że czas wykonania wyszukiwania binarnego jest $\mathrm{\Theta }({\log }_{2}n)$‍ we wszystkich przypadkach. Na przykład, może się zdarzyć, że zgadniemy w pierwszej próbie, a wtedy czas wykonania będzie $\mathrm{\Theta }(1)$‍. Cas wykonania algorytmu wyszukiwania binarnego nie jest dłuższy, niż $\mathrm{\Theta }({\log }_{2}n)$‍, 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 $k\cdot f(n)$‍ dla pewnej zmiennej $k$‍. Oto jak patrzeć na czas, który jest ograniczony przez $O(f(n))$‍:

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({\log }_{2}n)$‍. Możemy użyć silniejszego twierdzenia w stosunku do czasu wykonania w najgorszym przypadku, czyli: $\mathrm{\Theta }({\log }_{2}n)$‍. Ale w ogólnym przypadku najsilniejsze stwierdzenie, które możemy zrobić jest takie, że wyszukiwanie binarne wykonuje się w czasie $O({\log }_{2}n)$‍.

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 $\mathrm{\Theta }(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 $\mathrm{\Theta }({\log }_{2}n)$‍, to oszacowanie $O({\log }_{2}n)$‍ 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({\log }_{2}n)$‍ ale nie zawsze wykonuje się w czasie $\mathrm{\Theta }({\log }_{2}n)$‍.

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(n^2)$‍, $O(n^3)$‍, czy $O(2^n)$‍. Natomiast żadne z oszacowań $\mathrm{\Theta }(n)$‍, $\mathrm{\Theta }(n^2)$‍, $\mathrm{\Theta }(n^3)$‍, oraz $\mathrm{\Theta }(2^n)$‍ 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.