Funkcje w notacji asymptotycznej

Kiedy używamy notacji asymptotycznej w celu zobrazowania tempa wzrostu czasu wykonywania algorytmu, wyrażanego wielkością zmiennej wejściowej $n$‍, warto mieć kilka rzeczy na uwadze.

Zacznijmy od czegoś prostego. Załóżmy, że algorytm potrzebuje stałą ilość czasu, niezależnie od wielkości zmiennej wejściowej. Na przykład, jeżeli otrzymałeś tablicę, która jest już posortowana w kolejności rosnącej i trzeba by znaleźć minimalny element, zajęłoby to stałą ilość czasu, ponieważ minimalny element musi być pod indeksem 0. Z uwagi na to, że chcemy wykorzystać funkcję zmiennej $n$‍ w notacji asymptotycznej, można powiedzieć, że ten algorytm działa w $\mathrm{\Theta }(n^0)$‍ czasie. Dlaczego? Ponieważ $n^0=1$‍ i czas działania algorytmu mieści się w zakresie stałej 1. W praktyce, nie piszemy $\mathrm{\Theta }(n^0)$‍, ale $\mathrm{\Theta }(1)$‍.

Załóżmy, że czas, potrzebny na wykonanie algorytmu można szacować jako $\mathrm{\Theta }({\log }_{10}n)$‍. Możemy również powiedzieć, że czas był $\mathrm{\Theta }({\log }_{2}n)$‍. Jak długo podstawa logarytmu jest stałą, nie ma znaczenia jakiej podstawy użyjemy w notacji asymptotycznej. Dlaczego nie? Ponieważ istnieje następujący wzór matematyczny:

dla wszystkich liczb dodatnich $a$‍,$b$‍ oraz $n$‍. W związku z tym, jeżeli $a$‍ i $b$‍ są stałymi, to ${\log }_{a}n$‍ i ${\log }_{b}n$‍ różnią się tylko współczynnikiem ${\log }_{b}a$‍, i jest to wspóczynnik, który możemy pominąć w notacji asymptotycznej.

Możemy zatem powiedzieć, że w najgorszym wypadku, czas wykonywania algorytmu wyszukiwania binarnego to $\mathrm{\Theta }({\log }_{a}n)$‍ dla każdej dodatniej stałej $a$‍. Dlaczego? Liczba prób to co najwyżej ${\log }_{2}n+1$‍, generowanie i testowanie każdej próby zabiera stałą ilość czasu, i definiowanie oraz zwracanie zajmuje również stałą ilość czasu. W praktyce piszemy, że wyszukiwanie binarne zajmuje $\mathrm{\Theta }({\log }_{2}n)$‍ czasu ponieważ informatycy lubią myśleć w kategoriach potęgi z 2.

Dla funkcji, których często używamy podczas analizy algorytmów używając notacji asymptotycznej istnieje pewien porządek. Jeżeli $a$‍ oraz $b$‍ są stałe i $a<b$‍, wtedy czas wykonania wynosi $\mathrm{\Theta }(n^a)$‍ rośnie wolniej niż czas wykonania $\mathrm{\Theta }(n^b)$‍. Na przykład, czas wykonania $\mathrm{\Theta }(n)$‍, który wynosi $\mathrm{\Theta }(n^1)$‍, rośnie wolniej niż czas wykonania $\mathrm{\Theta }(n^2)$‍. Wykładniki nie muszą nawet być liczbami całkowitymi. Na przykład, czas wykonania $\mathrm{\Theta }(n^2)$‍ rośnie wolniej niż czas wykonania $\mathrm{\Theta }(n^2\sqrt{n})$‍, który wynosi $\mathrm{\Theta }(n^{2.5})$‍.

Na poniższym wykresie porównano tempo wzrostu $n$‍,$n^2$‍, oraz $n^{2,5}$‍:

Logarytmy rosną wolniej niż wielomiany. Oznacza to, że $\mathrm{\Theta }({\log }_{2}n)$‍ rośnie wolniej niż $\mathrm{\Theta }(n^a)$‍ dla każdej dodatniej stałej $a$‍. Ale ponieważ wartość ${\log }_{2}n$‍ zwiększa się ze wzrostem $n$‍, $\mathrm{\Theta }({\log }_{2}n)$‍ rośnie szybciej niż $\mathrm{\Theta }(1)$‍.

Na poniższym wykresie porównano tempo wzrostu $1$‍,$n$‍, oraz ${\log }_{2}n$‍:

Oto lista funkcji w notacji asymptotycznej, z którymi mamy często do czynienia podczas analizowania algorytmów, w kolejności od najwolniej do najszybciej rosnących.

Należy zauważyć, że funkcja wykładnicza $a^n$‍, gdzie $a>1$‍, rośnie szybciej niż jakakolwiek funkcja wielomianowa $n^b$‍, gdzie $b$‍ jest stałą.

Ta lista nie jest oczywiście pełna, jest wiele funkcji, które opisują złożoności obliczeniowe czy czasy wykonania różne od tych powyżej. Zapewne napotkasz niektóre z nich w swojej podróży przez krainę informatyki.

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.