If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Notacja 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 z tablica.length
  • porównaj array[próba] z szukanaWartość
  • 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 c1n, gdzie c1 jest sumą czasów wykonania wszystkich poleceń wewnątrz pętli w jednej iteracji. Nie możemy powiedzieć, ile dokładnie wynosi c1, 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łą c2. A zatem, całkowity czas wyszukiwania liniowego w najgorszym przypadku wynosi c1n+c2.
Jak już stwierdziliśmy, stały współczynnik c1 oraz współczynnik niższego rzędu c2 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 Θ(n). 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 Θ(n), mówimy, że kiedy n stanie się wystarczające duże, czas wykonania wynosi, co najmniej k1n i co najwyżej k2n, dla niektórych stałych k1 oraz k2. Oto jak możemy myśleć o Θ(n):
Dla małych wartości n, nie interesuje nas jak porównujemy czas wykonania z k1n czy z k2n. 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 k1n oraz k2n. Jeśli potrafimy wskazać stałe k1 oraz k2, to możemy powiedzieć, że czas wykonania wynosi Θ(n).
Nie ograniczamy się jedynie do n w zapisie duże-Θ. Możemy użyć dowolnej funkcji, takiej jak n2, nlog2 n lub wszelkich innych funkcji n. Oto jak możemy myśleć o czasie wykonania pewnego algorytmu, który jest Θ(f(n)) dla pewnej funkcji f(n):
Gdy n stanie się odpowiednio duże, czas wykonania będzie znajdował się pomiędzy k1f(n) oraz k2f(n).
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 6n2+100n+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 i stwierdzasz jedynie, że czas wykonania wynosi Θ(n2).
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
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.