[ Pobierz całość w formacie PDF ]
wywołaniami rekurencyjnymi o takich samych właściwościach. Oznacza to, że one
również składają się z trzech składników, z których dwa są rekurencyjne, itd.
Pomysł polega na zbudowaniu drzewka, którego węzły reprezentowałyby znane znam,
stałe składniki, zaś krawędzie (gałęzie) - wywołania rekurencyjne. Na początku takie
drzewo wyglądałoby dość skromnie:
Schemat 1. Drzewo rekursji dla złożoności praktycznej ciągu Fibonacciego - etap pierwszy
Nietrudno je jednak rozbudować. Ukryte za wielokropkami poddrzewa tworzymy
bowiem& rekurencyjnie - z tym, że teraz T(n-1) lub T(n-2) pełnią rolę T(n):
Schemat 2. Drzewo rekursji dla złożoności praktycznej ciągu Fibonacciego - etap drugi
W podobny sposób budujemy drzewko, aż dojdziemy do liści, czyli węzłów na końcach
wywołań T(2) lub T(1). Po zsumowaniu wartości we wszystkich węzłach drzewa
otrzymamy liczbę kroków algorytmu potrzebnych do obliczenia n-tej liczby Fibonacciego.
Stąd już bardzo blisko do określenia klasy tego algorytmu.
Schemat 3. Gotowe drzewo rekursji dla złożoności praktycznej ciągu Fibonacciego
W naszym przypadku w węzłach mamy wyłącznie jedynki, zatem problem sprowadza się
do określenia ich ilości. W tym celu wyobrazmy sobie, jak wygląda drzewko dla wartości
T(3) - jest to pierwsza wartość, dla której występują składniki rekurencyjne. Drzewo
będzie miało wyłącznie jedno rozgałęzienie, wysokość 1 i dwa poziomy. Generalnie
można stwierdzić, że dla danego n drzewo T(n) ma wysokość n-2 oraz n-1 poziomów.
A ile jest węzłów na każdym poziomie?& Na pierwszym mamy oczywiście jeden korzeń;
na drugim są już dwa węzły, odpowiadające dwóm wywołaniom rekurencyjnym. Od
każdego z nich odchodzą po dwie krawędzie, zatem na trzecim poziomie mamy cztery
węzły, i tak dalej - schodząc niżej, (zazwyczaj) podwajamy ilość węzłów. A ponieważ
liczba poziomów drzewa wynosi n-1, na ostatnim poziomie będzie więc mniej więcej 2n-1
liści, zaś na i-tym - około 2i-1 węzłów.
Nie możemy dokładnie określić tych wartości, gdyż drzewo nie zawsze jest
zrównoważone. Z grubsza rzecz biorąc znaczy to, że najniższy poziom nie zawsze zawiera
wszystkie liście drzewa. Przykładem może być np. drzewko dla T(4). Liczba liści różni się
jednak co najwyżej o stałą, zatem nie wpływa to na złożoność asymptotyczną.
By uzyskać przybliżoną ilość węzłów w drzewie należy oczywiście zsumować ich ilości na
wszystkich n-1 poziomach:
n-1 n
i i
1+ 2 + 4 + 8 +& + 2n-1 = = - 2n = 2n+1 - 2n = 2n
"2 "2
i=0 i=0
Otrzymujemy funkcję wykładniczą względem n. Możemy zatem stwierdzić, że złożoność
rekurencyjnego algorytmu dla ciÄ…gu Fibonacciego to aż Ÿ(2n).
Post scriptum: algorytm iteracyjny dla ciÄ…gu Fibonacciego
Rekurencyjna procedura obliczania ciągu jest więc skrajnie nieefektywna. W sumie nie
jest to powód do jakiegoś szczególnego zmartwienia, bo jest spora szansa, że ów ciąg nie
będzie ci nigdy do niczego potrzebny. Jeśli jednak zdarzy się inaczej, to zdecydowanie
powinieneś wtedy poszukać innego rozwiązania.
Problem z rekurencją polega tutaj na tym, iż większość wyrazów jest obliczana
wielokrotnie, przez co mnóstwo czasu procesora po prostu się marnuje. Procedura ta jest
po prostu mało inteligentna. W takich wypadkach stosuje się technikę zwaną
programowaniem dynamicznym, która generalnie jest troszkę skomplikowana. W tym
przypadku wystarczy jednak wykazać się tylko odrobiną sprytu: po co za każdym razem
liczyć każdy wyraz od początku, skoro można zapisywać wyniki pośrednie? Nie będzie to
zużywało wiele pamięci, gdyż musimy znać jedynie dwa poprzedzające wyrazy.
Iteracyjny algorytm obliczania ciągu Fibonacciego może więc wyglądać tak:
unsigned Fib(unsigned n)
{
unsigned uFib, uFib1, uFib2;
// warunki brzegowe
uFib = uFib1 = uFib2 = 1;
// liczymy po kolei wyrazy aż do żądanego
for (unsigned i = 3; i
{
// "przewijamy" dwa wyrazy poprzedzajÄ…ce
uFib2 = uFib1;
uFib1 = uFib;
// obliczamy nowy wyraz
uFib = uFib1 + uFib2;
}
// zwracamy wynik
return uFib;
}
Różnica jest kolosalna. Z pobieżnego rzutu oka na pętlę w powyższej funkcji wynika
bowiem, że jest ona rzÄ™du zaledwie Ÿ(n)! Wersja iteracyjna pozwala wiÄ™c zejść ze
złożoności wykładniczej do liniowej.
Rekurencja w technice dziel i zwyciężaj
Jeżeli nie miałeś wcześniej do czynienia z algorytmami rekurencyjnymi, to poprzednim
paragrafem mogłem cię do nich nieco zniechęcić. Nie powinieneś jednak brać ich sobie
za bardzo do serca. W rzeczy samej rekurencja nie jest wcale takim diabłem, jakim to
trochę niechcący przedstawiłem ją wcześniej. Co ważniejsze, istnieje wiele problemów,
dla których tylko algorytmy oparte na rekursji dają efektywne albo wręcz jedyne
poprawne rozwiÄ…zanie.
Pokazną grupę stanowią tutaj operacje na strukturach danych, które same w sobie mają
naturę rekurencyjną. Przykładem mogą być grafy i drzewa, a praktycznym
zastosowaniem - chociażby wyszukiwanie pliku o określonej nazwie w rozległym drzewie
katalogów dyskowych.
Na rekurencji jest też oparta bardzo skuteczna i ogólna metoda projektowania
algorytmów, znana jako dziel i zwyciężaj (ang. divide & conquer). Jej idea polega na
podziale zadania na mniejsze i kontynuowanie tego procesu aż do momentu uzyskania
problemu elementarnego, który potrafimy rozwiązać bezpośrednio. W sumie algorytm
korzystający z tej metody składa się z trzech części:
podzielenia problemu na mniejsze fragmenty (podproblemy)
rozwiązania podproblemów poprzez dalszy, rekurencyjny podział - aż dojdziemy
do przypadku elementarnego, niepodzielnego
złączenia rozwiązań podproblemów w jedno rozwiązanie całego problemu
Opis ten może brzmi nieco zawile, lecz sama idea kryjąca się za nim jest w gruncie
rzeczy bardzo prosta. Jak to czesto bywa, najlepiej zobaczyć ją na przykładzie. Ponownie
pozwolę sobie na wykorzystanie w tym celu sortowania, jako że czynność ta jest dla
komputerów zapewne tak samo naturalna, jak dla nas oddychanie czy jedzenie. Na
[ Pobierz całość w formacie PDF ]