ALG0

70 Rozdział 3. Analiza sprawności algorytmów

Przykład: SRL=x_n-3x„.i+2 x„ -2=0 daje R(x)=x’-3x+2=(x-l)(x-2).

Otrzymane powyżej współczynniki A, posłużą do skonstruowania tzw. rozwiązania ogólnego RO liniowego równania rekurencyjnego:

RO^P/A.

Dodatkowo będziemy potrzebować tzw. rozwiązania szczególnego RS linio* wego równania rekurencyjnego Jego postać zależy od formy, jaką przybiera reszta u(n,m). Oto możliwe przypadki:

• Jeśli u(n,m)=0, to:

RS=0.

• Jeśli ii(n.in) jest wielomianem stopnia m i zmiennej n oraz 1 (jeden) nie jest rozwiązaniem RC, wówczas:

RS-O(n.m),

gdzie: Q(n,rn) jest pewnym wielomianem stopnia m i zmiennej n, o współczynnikach nieznanych (do odnalezienia).

• Jeśli u(n,rn) jest wielomianem stopnia iii i zmiennej ii oraz 7 jest rozwiązaniem RC, wtedy:

RS= ri'Q(n,m),

gdzie: /z jest stopniem pierwiastka.

Przykładowo, jeśli jedynka jest pierwiastkiem pojedynczym RC, to p=I, jeśli pierwiastkiem podwójnym, top—2 itd.

• Jeśli u(n,m)=a" i a nie jest rozwiązaniem RC, wtedy:

RS=caⁿ.

• Jeśli u(n.m)= a" i a jest pierwiastkiem stopnia p RC, wtedy:

RS=ca’rf.

• Jeśli u(n,m) o."fV(n,m) i a nie jest rozwiązaniem RC (tradycyjnie już W(n,m) jest pewnym wielomianem stopnia m i zmiennej n), będziemy wówczas mieli: RS= a"S(n,m.),

gdzie: S(n,m) jest pewnym wielomianem stopnia m i zmiennej n.

Uwaga: występujące po prawej stronie wzorów wielomiany i stałe mają cha-rakter zmiennych, które należy odnaleźć!_

Rozwiązaniem równania rekurencyjnego jest suma obu równań: ogólnego i szczególnego.

ALG0

ALG0

RO^P/A.

ALG0

ALG0