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 czytaALG4 64 Rozdział 3. Analiza sprawności algorytmów3.4. Przykład 3: Wpadamy w pułapkę Zadania z dwóchALG4 54 Rozdział 3. Analiza sprawności algorytmów Tematyką tego rozdziału jest tzw. złożoność oblicALG6 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 zostALG8 68 Rozdział 3. Analiza sprawności algorytmów3.6. Nowe zadanie: uprościć obliczenia! Nic sposóbALG2 72 Rozdział 3. Analiza sprawności algorytmówn o) = i, i = A + O, A = 1. Po tALG4 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ównanieALG2 12 PrzedmowaRozdział 3 Analiza sprawności algorytmów Przegląd najpopularniejszych i najprostszALG3 Rozdział 3Analiza sprawności algorytmów Podstawowe kryteria pozwalające na wybór właściwego alALG8 58Rozdział 3. Analiza sprawności algorytmów konania programu zależy od danej wejściowej n? W lALG 0 90 Rozdział 4. Algorytmy sortowania 90 Rozdział 4. Algorytmy sortowania Rys. 4 - 8. SortowanieALG0 190 Rozdział 7. Algorytmy przeszukiwania Odnalezienie liczby .1 w tablicy tub jest sygnalizowa12 PrzedmowaRozdział 3 Analiza sprawności algorytmów Przegląd najpopularniejszych i najprostszychBild0 90 Rozdział 3 analizowaniu historii partii oraz różnorodnych opinii na jej temat, a w szczegówięcej podobnych podstron