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=hk sprowadzające równanie nieliniowe do równania (bj: uT(bl l)+d(bk). Podstawiając ponadto i^-T(bk) 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;
Wyszukiwarka
Podobne podstrony:
ALG1 3.7. Analiza programów rekurencyjnych 71 Cały ten bagaż wzorów był naprawdę niezbędny! Dla zil
ALG5 3.7. Analiza programów rekurencyjnych 75 otrzymując w efekcie: =26„_, +3log, 3} _ frównanie li
ALG9 3.7. Analiza programów rekurencyjnych 69 W tym paragrafie przedstawiona zostanie metoda mająca
ALG1 2.B. Typy programów rekurencyjnych 41 if (x==0) return 1; else return x*silnial !x-l); t Nie j
PSYCHOLOGICZNA ANALIZA POSTAW PRACOWNIKÓW DPS 71 Z tabeli 7 wynika, że związek wszystkich czterech z
Widać już, że rozwiązanie (3.1) ma postać= azr=i(i-a) n-(.aibo Y,p = nY, + a(l - a)y,_, + (1 - a)2Y,
ALG3 2.3. Jak wykonują się programy rekurencyjne? 332.3. Jak wykonują się programy rekurencyjne? Do
ALG3 2.7. Myślenie rekurencyjne 43 Rckurcncyjność naszego zadania jest oczywista, bowiem program wy
Scan3 _Analiza złożonego programu w zapisie STL Założenie: Kurs Podstawowy S7 Analiza programu
ALG3 1.3. Proces koncepcji programów 23 pisania jednej linii kodu. Pomijając już jednak tego typu s
ALG2 32 Rozdział 2. Rekurencja Wyżej podaliśmy warunki pozytywnego zakończenie programu. W przypadk
ALG6 36 Rozdział 2. Rekurencja każemy. W rozdziale 9 zostanie omówiona ciekawa technika programowan
ALG0 50_ _Rozdział2. Rekurencja Odpowiadający temu rozumowaniu program przedstawia się
ALG3 6.3. Kilka przykładów derekursywacji algorytmów 173 Pokaźna grupa procedur rekurencyjnych dość
więcej podobnych podstron