Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 3: Asymptotyczne tempo wzrostuNotacja duże-θ (duże-Theta)
Spójrzmy na prostą realizację wyszukiwania liniowego:
var wykonajWyszukiwanieLiniowe = function(tablica, szukanaWartość) {
for (var proba = 0; proba < tablica.length; proba++) {
if (tablica[proba] === szukanaWartosc) {
return proba; // znaleźliśmy szukaną wartość!
}
}
return -1; // nie udało się znaleźć szukanej wartości
};
Oznaczmy długość naszej macierzy (
tablica.length
) przez n. Największa liczba wywołań pętli for w tym programie wynosi 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:
- porównaj wartość
próba
ztablica.length
- porównaj
array[próba]
zszukanaWartość
- ewentualnie zwróć wartość
próba
- zwiększ
próba
o 1.
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 razy, czas wykonania wszystkich n iteracji wynosi c, start subscript, 1, end subscript, dot, n, gdzie 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, 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, start subscript, 2, end subscript. A zatem, całkowity czas wyszukiwania liniowego w najgorszym przypadku wynosi c, start subscript, 1, end subscript, dot, n, plus, c, start subscript, 2, end subscript.Jak już stwierdziliśmy, stały współczynnik c, start subscript, 1, end subscript oraz współczynnik niższego rzędu 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. Zapisu, jakiego używamy dla tego czasu wykonania to \Theta, left parenthesis, n, right parenthesis. Jest to grecka litera "theta", a wyrażenie te wymawiamy "duże-theta z n" lub tylko "Theta z n".
Kiedy mówimy, że określony czas wykonania wynosi \Theta, left parenthesis, n, right parenthesis, mówimy, że kiedy n stanie się wystarczające duże, czas wykonania wynosi, co najmniej k, start subscript, 1, end subscript, dot, n i co najwyżej k, start subscript, 2, end subscript, dot, n, dla niektórych stałych k, start subscript, 1, end subscript oraz k, start subscript, 2, end subscript. Oto jak możemy myśleć o \Theta, left parenthesis, n, right parenthesis:
Dla małych wartości n, nie interesuje nas jak porównujemy czas wykonania z k, start subscript, 1, end subscript, dot, n czy z k, start subscript, 2, end subscript, dot, n. Ale kiedy 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, start subscript, 1, end subscript, dot, n oraz k, start subscript, 2, end subscript, dot, n. Jeśli potrafimy wskazać stałe k, start subscript, 1, end subscript oraz k, start subscript, 2, end subscript, to możemy powiedzieć, że czas wykonania wynosi \Theta, left parenthesis, n, right parenthesis.
Nie ograniczamy się jedynie do n w zapisie duże-Θ. Możemy użyć dowolnej funkcji, takiej jak n, squared, n, log, start base, 2, end base n lub wszelkich innych funkcji n. Oto jak możemy myśleć o czasie wykonania pewnego algorytmu, który jest \Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis dla pewnej funkcji f, left parenthesis, n, right parenthesis:
Gdy n stanie się odpowiednio duże, czas wykonania będzie znajdował się pomiędzy k, start subscript, 1, end subscript, dot, f, left parenthesis, n, right parenthesis oraz 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 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 100, n, plus, 300 i stwierdzasz jedynie, że czas wykonania wynosi \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. "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.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji