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(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. Nie jest jednak prawdą że czas wykonania wyszukiwania binarnego jest $\Theta(\log_2 n)$\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(1)$\Theta, left parenthesis, 1, right parenthesis. Cas wykonania algorytmu wyszukiwania binarnego nie jest dłuższy, niż $\Theta(\log_2 n)$\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(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, to dla odpowiednio dużych $n$n czas wykonania wynosi co najwyżej $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis dla pewnej zmiennej $k$k. Oto jak patrzeć na czas, który jest ograniczony przez $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:

Możemy powiedzieć, że czas wykonania wynosi "duże-O z $f(n)$f, left parenthesis, n, right parenthesis lub po prostu "O z $f(n)$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(\log_2 n)$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(\log_2 n)$\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(\log_2 n)$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(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis w danej sytuacji, to ten czas jest również $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Na przykład, jeśli najdłuższy czas wyszukiwania binarnego wynosi $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, to oszacowanie $O (\log_2 n)$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(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis ale nie zawsze wykonuje się w czasie $\Theta(\log_2 n)$\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(n)$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$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)$O, left parenthesis, n, right parenthesis jest górnym ograniczeniem na czas wykonania wyszukiwania binarnego. Inne, podobnie nieprecyzyjne oszacowania mają postać $O(n^2)$O, left parenthesis, n, squared, right parenthesis, $O(n^3)$O, left parenthesis, n, cubed, right parenthesis, czy $O(2^n)$O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. Natomiast żadne z oszacowań $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis, $\Theta(n^3)$\Theta, left parenthesis, n, cubed, right parenthesis, oraz $\Theta(2^n)$\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.