ALG8

58

Rozdział 3. Analiza sprawności algorytmów

konania programu zależy od danej wejściowej n? W lym celu spróbujmy rozpisać równania:

T{n) =		+ T(n -	1).
T{n-\) =	<c	+ T(n -	2),
T{n - 2) =	te	+ T(n-	35,
7X1) -	t,	-f ;s O
7(0) =

Jeśli dodamy je teraz stronami, to powinniśmy otrzymać:

T(n) + T(n -1)+- • •+f(0) = (n + 1 )t_c + T(n-1)+- ■ -+7'(0),

co powinno dać, po zredukowaniu składników identycznych po obu stronach równości, następującą zależność:

T(n) = (n +1)/₍.

Jest to funkcja, która w satysfakcjonującej, nieskomplikowanej formie pokazuje, w jaki sposób rozmiar danej wejściowej wpływa na ilość instrukcji porównań wykonanych przez program - czyli de facto na czas wykonania algorytmu. Znając bowiem parametr /₍ i wartość n możemy powiedzieć dokładnie w ciągu ilu sekund (minut, godzin, lat...) wykona się algorytm na określonym komputerze.

Tego typu rezultat dokładnych obliczeń zwykło się nazywać złożonością praktyczną algorytmu, funkcja ta jest zazwyczaj oznaczana tak jak wyżej, przez T.

W praktyce rzadko interesuje nas aż tak dokładny wynik. Niewiele bowiem się zmieni, jeśli zamiast T(n)=(n+l)t_c otrzymamy T(n)=(n+3)l_c\

Do czego zmierzam? Otóż w dalszych rozważaniach będziemy głównie szukać odpowiedzi na pytanie:

Jaki typ funkcji matematycznej, występującej w zależności określającej złożoność praktyczną programu, odgrywa w niej najważniejszą rolę, wpływając najsilniej na czas wykonywania programu?_