5996833054

Parametrem najczęściej decydującym o czasie wykonania algorytmu jest rozmiar danych, z którymi ma on do czynienia.

Parametr ten może mieć różne znaczenie:

-    dla funkcji sortującej tablicę parametrem będzie rozmiar tablicy

-    dla funkcji liczącej n! będzie to wielkość danej wejściowej

W algorytmie zawsze można wyróżnić tzw. operacje dominujące (najbardziej czasochłonne) - takie, że łączna ich liczba jest proporcjonalna do liczby wszystkich operacji jednostkowych w dowolnej realizacji algorytmu.

Dla sortowania operacją tą będzie zwykle porównanie dwóch elementów, czasem także przestawienie elementów ciągu.

Jednostką złożoności czasowej jest czas wykonania jednej operacji dominującej.

Wyróżniamy:

-    złożoność pesymistyczną W(n) - zdefiniowaną jako ilość zasobów komputerowych, potrzebnych przy "najgorszych" danych wejściowych rozmiaru n

-    złożoność oczekiwaną A(n) - definiowaną jako ilość zasobów komputerowych, potrzebnych przy "typowych" danych wejściowych rozmiaru n

Faktyczna/praktyczna złożoność czasowa algorytmu (czas działania) różni się od wyliczonej teoretycznie współczynnikiem proporcjonalności zależnym od konkretnej realizacji algorytmu. Istotną informacją zawarta w W(n), A(n) jest rząd wielkości, czyli zachowanie asymptotyczne, gdy n -> oc .

Będziemy zatem szukać złożoności teoretycznej, ti. funkcji matematycznej występującej w T(n), która odgrywa w niej najważniejszą rolę, wpływając najsilniej na czas wykonania programu.