Notacja duże-θ (duże-Theta)

Spójrzmy na prostą realizację wyszukiwania liniowego:

Oznaczmy długość naszej macierzy (tablica.length) przez $n$n. Największa liczba wywołań pętli for w tym programie wynosi $n$n i ten najgorszy przypadek zachodzi, gdy poszukiwanej przez nas wartości nie ma w macierzy, którą przeszukujemy.

Za każdym wywołaniem pętli for wykonywane są różne operacje:

Za każdym razem, gdy jest wykonywane, każde z tych nieskomplikowanych obliczeń zajmuje pewien stały okres. Jeśli wykonujemy pętle for $n$n razy, czas wykonania wszystkich $n$n iteracji wynosi $c_1 \cdot n$c, start subscript, 1, end subscript, dot, n, gdzie $c_1$c, start subscript, 1, end subscript jest sumą czasów wykonania wszystkich poleceń wewnątrz pętli w jednej iteracji. Nie możemy powiedzieć, ile dokładnie wynosi $c_1$c, start subscript, 1, end subscript, ponieważ zależy to od wielu czynników: szybkości procesora, języka programowania, w którym zakodowano pętle, rodzaju kompilatora lub interpretera, który przekłada program na polecenia zrozumiałe dla procesora, i tak dalej.

Wykonanie tego kodu wiąże się z dodatkowymi kosztami, związanymi z inicjalizacją pętli for (w tym także przypisanie pierwszej próbie wartości 0), oraz zwracanie, w niektórych przypadkach, -1 po zakończeniu wykonywania. Oznaczmy te dodatkowe koszty jako kolejną stałą $c_2$c, start subscript, 2, end subscript. A zatem, całkowity czas wyszukiwania liniowego w najgorszym przypadku wynosi $c_1 \cdot n + c_2$c, start subscript, 1, end subscript, dot, n, plus, c, start subscript, 2, end subscript.

Jak już stwierdziliśmy, stały współczynnik $c_1$c, start subscript, 1, end subscript oraz współczynnik niższego rzędu $c_2$c, start subscript, 2, end subscript nie mówią nam o tempie wzrostu czasu wykonania. Istotne jest to, że najgorszy czas wyszukiwania liniowego rośnie tak samo jak rozmiar tablicy $n$n. Zapisu, jakiego używamy dla tego czasu wykonania to $\Theta(n)$\Theta, left parenthesis, n, right parenthesis. Jest to grecka litera "theta", a wyrażenie te wymawiamy "duże-theta z $n$n" lub tylko "Theta z $n$n".

Kiedy mówimy, że określony czas wykonania wynosi $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, mówimy, że kiedy $n$n stanie się wystarczające duże, czas wykonania wynosi, co najmniej $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n i co najwyżej $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n, dla niektórych stałych $k_1$k, start subscript, 1, end subscript oraz $k_2$k, start subscript, 2, end subscript. Oto jak możemy myśleć o $\Theta(n)$\Theta, left parenthesis, n, right parenthesis:

Dla małych wartości $n$n, nie interesuje nas jak porównujemy czas wykonania z $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n czy z $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n. Ale kiedy $n$n staje się wystarczająco duże – na linii przerywanej lub po jej prawej stronie – czas wykonania musi być ograniczony od góry i od dołu przez $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n oraz $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n. Jeśli potrafimy wskazać stałe $k_1$k, start subscript, 1, end subscript oraz $k_2$k, start subscript, 2, end subscript, to możemy powiedzieć, że czas wykonania wynosi $\Theta(n)$\Theta, left parenthesis, n, right parenthesis.

Nie ograniczamy się jedynie do $n$n w zapisie duże-Θ. Możemy użyć dowolnej funkcji, takiej jak $n^2$n, squared, $n \log_2$n, log, start base, 2, end base n lub wszelkich innych funkcji $n$n. Oto jak możemy myśleć o czasie wykonania pewnego algorytmu, który jest $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis dla pewnej funkcji $f(n)$f, left parenthesis, n, right parenthesis:

Gdy $n$n stanie się odpowiednio duże, czas wykonania będzie znajdował się pomiędzy $k_1 \cdot f(n)$k, start subscript, 1, end subscript, dot, f, left parenthesis, n, right parenthesis oraz $k_2 \cdot f(n)$k, start subscript, 2, end subscript, dot, f, left parenthesis, n, right parenthesis.

W praktyce odrzucamy tylko stałe współczynniki oraz wyrażenia niższego rzędu. Kolejną zaletą korzystania z notacji duże-Θ jest to, że nie musimy martwić się, jakich jednostek czasu używamy. Na przykład, załóżmy, że wyliczyłeś czas wykonania, który wynosi $6n^2 + 100n + 300$6, n, squared, plus, 100, n, plus, 300 mikrosekund. A może milisekund. Kiedy korzystasz z notacji duże-Θ nie martwisz się o jednostki. Odrzucasz również współczynnik 6 oraz wyrażenia niższego rzędu $100n + 300$100, n, plus, 300 i stwierdzasz jedynie, że czas wykonania wynosi $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis.

Kiedy używamy notacji duże-Θ, mówimy wówczas, że czas wykonania jest mocno związany asymptotycznie. "Asymptotycznie" ponieważ ma on znaczenie jedynie dla dużych wartości $n$n. "Mocno związany" ponieważ jest umiejscowiony powyżej i poniżej dwóch stałych współczynników.

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.