ALG0

ALG0



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

Przykład: SRL=xn-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=can.

   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.


Wyszukiwarka

Podobne podstrony:
Alg0 60 Rozdział 3. Analiza sprawności algorytmów •    Znak graficzny 3 należy czyta
ALG4 64 Rozdział 3. Analiza sprawności algorytmów3.4. Przykład 3: Wpadamy w pułapkę Zadania z dwóch
ALG4 54 Rozdział 3. Analiza sprawności algorytmów Tematyką tego rozdziału jest tzw. złożoność oblic
ALG6 56 Rozdział 3. Analiza sprawności algorytmów jest intuicyjnie bardzo proste, dalej będziemy uż
ALG2 52 Rozdział 3. Analiza sprawności algorytmów Rys. 3 -
ALG6 66 Rozdział 3. Analiza sprawności algorytmów return pos; else    //element zost
ALG8 68 Rozdział 3. Analiza sprawności algorytmów3.6. Nowe zadanie: uprościć obliczenia! Nic sposób
ALG2 72 Rozdział 3. Analiza sprawności algorytmówn o) = i, i = A + O, A =    1. Po t
ALG4 74 Rozdział 3. Analiza sprawności algorytmów • funkcja d(n) musi spełniać następującą własność
ALG6 76 Rozdział 3. Analiza sprawności algorytmów Analogicznie dla 2 otrzymamy: Vn > 1, A(n,2) =
ALG8 78___Rozdział 3 Analiza sprawności algorytmówZad. 3-4 Proszę rozwiązać następujące równanie
ALG2 12 PrzedmowaRozdział 3 Analiza sprawności algorytmów Przegląd najpopularniejszych i najprostsz
ALG3 Rozdział 3Analiza sprawności algorytmów Podstawowe kryteria pozwalające na wybór właściwego al
ALG8 58Rozdział 3. Analiza sprawności algorytmów konania programu zależy od danej wejściowej n? W l
ALG 0 90 Rozdział 4. Algorytmy sortowania 90 Rozdział 4. Algorytmy sortowania Rys. 4 - 8. Sortowanie
ALG0 190 Rozdział 7. Algorytmy przeszukiwania Odnalezienie liczby .1 w tablicy tub jest sygnalizowa
12 PrzedmowaRozdział 3 Analiza sprawności algorytmów Przegląd najpopularniejszych i najprostszych
Bild0 90 Rozdział 3 analizowaniu historii partii oraz różnorodnych opinii na jej temat, a w szczegó

więcej podobnych podstron