Dinamično programiranje/Fibonaccijevo zaporedje

Iz MaFiRaWiki

Fibonaccijevo zaporedje je definirano rekurzivno, zato je za izračun n-tega člena najbolj primerna rekurzivna metoda.

  1.  
  2. //metoda vrne n-ti člen Fibonaccijevega zaporedja
  3. public static int fibo(int n) {
  4. if(n == 0 || n == 1) return 1; //ustavitveni pogoj: prva dva člena imata vrednost 1
  5. //metodo kličemo rekurzivno dokler je n >= 2
  6. return fibo(n-1) + fibo(n-2);
  7. }

Vendar tako napisana metoda že za dokaj majhne n opravi precej nepotrebnega računanja. Če hočemo na primer izračunati peti člen zaporedja, se prvi člen računa kar štirikrat (metoda fibo se za n = 1 kliče štirikrat). Na spodnjem grafu se vidi, da tudi nekatere druge člene računamo večkrat.

Ker nekatere člene računamo večkrat, je časovna zahtevnost te metode eksponentna. Temu se lahko izognemo: ko metodo prvič pokličemo za neko število n, rezultat shranimo v npr. tabelo in ko spet potrebujemo rezultat metode pri tem istem n, ga vzamemo iz tabele. Ker nižjih členov ni potrebno računati večkrat, je časovna zahtevnost sedaj O(n). To je pristop od zgoraj navzdol: najprej smo problem razbili na podprobleme in potem podprobleme rešili in shranili rešitve. Kot že rečeno, shranjevanju vrednosti, ki smo jih že izračunali, pravimo memoizacija.

  1. // tabela, v kateri bomo hranili vrednosti že izračunanih členov
  2. // na i-tem mestu bo vrednost i-tega člena
  3. public static int[] fibonacci = new int[1000]; //zadostuje za izračun do 1000-ega člena zaporedja
  4.  
  5. public static int fibo(int n) {
  6. if(n<=1) return 1;
  7. else {
  8. if(fibonacci[n] == 0 ){//n-tega člena do sedaj še nismo izračunali
  9. fibonacci[n] = fibo(n-1) + fibo(n-2); //rezultat vstavimo v tabelo, da ga bomo lahko
  10. //kasneje spet uporabili
  11. }
  12. return fibonacci[n];
  13. }
  14. }

Tudi to metodo lahko še izboljšamo. Prostorsko zahtevnost lahko zmanjšamo z linearne na konstantno. Da nam ni potrebno definirati tabele, uporabimo pristop od spodaj navzgor: Člene računamo od drugega (ničti in prvi sta dana) do n-tega in ob vsaki ponovitvi zanke si zapomnimo samo vrednosti prejšnjih dveh členov.

  1.  
  2. public static int fibo2(int n){
  3. int fibo_0 = 1;
  4. int fibo_1 = 1;
  5. for(int i = n-1; i > 0; i--){
  6. int fiboNovi = fibo_0 + fibo_1;
  7. fibo_0 = fibo_1;
  8. fibo_1 = fiboNovi;
  9. }
  10. return fibo_1;
  11. }
Osebna orodja