Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 3: Asymptotyczne tempo wzrostuNotacja 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 . Nie jest jednak prawdą że czas wykonania wyszukiwania binarnego jest we wszystkich przypadkach. Na przykład, może się zdarzyć, że zgadniemy w pierwszej próbie, a wtedy czas wykonania będzie . Cas wykonania algorytmu wyszukiwania binarnego nie jest dłuższy, niż , 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 , to dla odpowiednio dużych czas wykonania wynosi co najwyżej dla pewnej zmiennej . Oto jak patrzeć na czas, który jest ograniczony przez :
Możemy powiedzieć, że czas wykonania wynosi "duże-O z lub po prostu "O z ". 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 . Możemy użyć silniejszego twierdzenia w stosunku do czasu wykonania w najgorszym przypadku, czyli: . Ale w ogólnym przypadku najsilniejsze stwierdzenie, które możemy zrobić jest takie, że wyszukiwanie binarne wykonuje się w czasie .
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 w danej sytuacji, to ten czas jest również . Na przykład, jeśli najdłuższy czas wyszukiwania binarnego wynosi , to oszacowanie jest także prawdziwe.
Twierdzenie odwrotne nie musi być prawdziwe: jak widzieliśmy, można powiedzieć, że wyszukiwanie binarne zawsze wykonuje się w czasie ale nie zawsze wykonuje się w czasie .
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 , jest jak najbardziej słuszne, dlatego że czas wykonania tego algorytmu rośnie nie szybciej niż pewna stała razy . 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 jest górnym ograniczeniem na czas wykonania wyszukiwania binarnego. Inne, podobnie nieprecyzyjne oszacowania mają postać , , czy . Natomiast żadne z oszacowań , , , oraz 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