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) \Theta(\log_2 n) . Nie jest jednak prawdą że czas wykonania wyszukiwania binarnego jest Θ(log2n) \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 Θ(1) \Theta(1) . Cas wykonania algorytmu wyszukiwania binarnego nie jest dłuższy, niż Θ(log2n) \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)) O(f(n)) , to dla odpowiednio dużych n n czas wykonania wynosi co najwyżej kf(n) k \cdot f(n) dla pewnej zmiennej k k . Oto jak patrzeć na czas, który jest ograniczony przez O(f(n)) O(f(n)) :
Możemy powiedzieć, że czas wykonania wynosi "duże-O z f(n) f(n) lub po prostu "O z f(n) 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) O(\log_2 n) . Możemy użyć silniejszego twierdzenia w stosunku do czasu wykonania w najgorszym przypadku, czyli: Θ(log2n) \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(log2n) 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 Θ(f(n)) \Theta(f(n)) w danej sytuacji, to ten czas jest również O(f(n)) O(f(n)) . Na przykład, jeśli najdłuższy czas wyszukiwania binarnego wynosi Θ(log2n) \Theta(\log_2 n) , to oszacowanie O(log2n) 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(log2n) O(\log_2 n) ale nie zawsze wykonuje się w czasie Θ(log2n) \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) O(n) , 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(n) jest górnym ograniczeniem na czas wykonania wyszukiwania binarnego. Inne, podobnie nieprecyzyjne oszacowania mają postać O(n2) O(n^2) , O(n3) O(n^3) , czy O(2n) O(2^n) . Natomiast żadne z oszacowań Θ(n) \Theta(n) , Θ(n2) \Theta(n^2) , Θ(n3) \Theta(n^3) , oraz Θ(2n) \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.
Ładowanie