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$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$n w notacji asymptotycznej, można powiedzieć, że ten algorytm działa w $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis czasie. Dlaczego? Ponieważ $n^0 = 1$n, start superscript, 0, end superscript, equals, 1 i czas działania algorytmu mieści się w zakresie stałej 1. W praktyce, nie piszemy $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis, ale $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

Załóżmy, że czas, potrzebny na wykonanie algorytmu można szacować jako $\Theta(\log_{10} n)$\Theta, left parenthesis, log, start base, 10, end base, n, right parenthesis. Możemy również powiedzieć, że czas był $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. 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$a,$b$b oraz $n$n. W związku z tym, jeżeli $a$a i $b$b są stałymi, to $\log_a n$log, start base, a, end base, n i $\log_b n$log, start base, b, end base, n różnią się tylko współczynnikiem $\log_b a$log, start base, b, end base, 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 $\Theta(\log_a n)$\Theta, left parenthesis, log, start base, a, end base, n, right parenthesis dla każdej dodatniej stałej $a$a. Dlaczego? Liczba prób to co najwyżej $\log_2 n + 1$log, start base, 2, end base, n, plus, 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 $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis 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$a oraz $b$b są stałe i $a < b$a, is less than, b, wtedy czas wykonania wynosi $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis rośnie wolniej niż czas wykonania $\Theta(n^b)$\Theta, left parenthesis, n, start superscript, b, end superscript, right parenthesis. Na przykład, czas wykonania $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, który wynosi $\Theta(n^1)$\Theta, left parenthesis, n, start superscript, 1, end superscript, right parenthesis, rośnie wolniej niż czas wykonania $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Wykładniki nie muszą nawet być liczbami całkowitymi. Na przykład, czas wykonania $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis rośnie wolniej niż czas wykonania $\Theta(n^2 \sqrt{n})$\Theta, left parenthesis, n, squared, square root of, n, end square root, right parenthesis, który wynosi $\Theta(n^{2.5})$\Theta, left parenthesis, n, start superscript, 2, point, 5, end superscript, right parenthesis.

Na poniższym wykresie porównano tempo wzrostu $n$n,$n^2$n, squared, oraz $n^{2{,}5}$n, start superscript, 2, comma, 5, end superscript:

Logarytmy rosną wolniej niż wielomiany. Oznacza to, że $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis rośnie wolniej niż $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis dla każdej dodatniej stałej $a$a. Ale ponieważ wartość $\log_2 n$log, start base, 2, end base, n zwiększa się ze wzrostem $n$n, $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis rośnie szybciej niż $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

Na poniższym wykresie porównano tempo wzrostu $1$1,$n$n, oraz $\log_2 n$log, start base, 2, end base, 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$a, start superscript, n, end superscript, gdzie $a > 1$a, is greater than, 1, rośnie szybciej niż jakakolwiek funkcja wielomianowa $n^b$n, start superscript, b, end superscript, gdzie $b$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.