ALG3

3.7. Analiza programów rekurencyjnych 73

7X1) = 1 + 1 = 2,

-2 + 7'

T(n) = 1 + 1 + 71

Widać już, że powyższy układ ni jak się ma do podanej poprzednio metody. W określeniu równania charakterystycznego przeszkadza nam owo dzielenie n przez 2. Otóż można z tej pułapki wybrnąć, np. przez podstawienie n=2p. ale ciąg dalszy obliczeń będzie dość złożony. Na całe szczęście matematycy zrobili w tym miejscu programistom miły prezent: bez żadnych skomplikowanych obliczeń można określić złożoność tego typu zadań, korzystając z kilku gotowych reguł. „Prezent'" ten jest tym bardziej cenny, że zadania o rozkładzie podobnym do powyższego występują bardzo często w praktyce programowania. Przed ostatecznym jego rozwiązaniem musimy zatem poznać jeszcze kilka wzorów matematycznych, ale obiecuję, że na tym już będzie koniec, jeśli chodzi o matematykę „wyższą”...

Załóżmy, że ogólna postać otrzymanego układu równań rekurencyjnych przedstawia się następująco:

7X1) = 1,

T(n) = aT\ -\ + d(n).

(Przy założeniu, że n>2 oraz a i b są pewnymi stałymi).

W zależności od wartości a, b i dfn) otrzymamy różne rozwiązania zgrupowane tablicy 3 - 3.

Tabela 3 - 3.

Czasy wykonania programów dla algorytmów różnej kłusy.

	Klasa algorytmu	Uwagi
a>d(b)	T(n)eO(n'°»"")
a<d(b)	T(n)s o(«^lo*^!''‘^/</’^))	gdy d(n) - n“ to T(n) e (tpf) = (\d(ri))
<i=d(b)	rDóeO^^log,. n)	j.Jy d(n)=n° to 7(n)e0(n" log„ «)

Wzory

te są wynikiem dość skomplikowanych v liczeń bazujących na następujących założeniach:

• n jest potęgą b, co pozwala wykona, podstawienie rt=h^k sprowadzające równanie nieliniowe do równania (bj^: uT(b^{l l})+d(b^k). Podstawiając ponadto i^-T(b^k) otrzymujemy rów tnie liniowe    + d(b ) z wa

runkiem początkowym t()-1. Dysku: t wyników tego równania prowadzi do wniosków końcowych, przedsta\ onyt h w tabeli 3-3;