fibonacci.java . Complexitati: O(n), O(2^n),O(n)

fibonacci.java

/*
Programare Dinamica
-------------------

Programarea dinamica (dezvoltata in 1950 de Bellman) esteo tehnica algoritmica ce conduce, de ce le mai multe ori, la un timp de calcul polinomial(O(n^2), O(n)). Spre deosebire de alte tehnici, 
ea furnizeaza intotdeauna solutia optima, dar nu se poate aplica oricarei probleme, ci doar celor care indepliplinesc anumite conditii.


Principiul de Optimalitate

Fundamentul programarii dinamice este principiul de OPTIMALITATE. 

Consideram o problema in care rezultatul se obtine ca urmare a unui sir de decizii:

D1, D2, D3, ..., Dn, care conduc sistemul prin starile S0 --> S1 --> S2, ---> Sn


Daca D1, D2, D3, ..., Dn conduce sistemul in mod optim din S0 in Sn, atunci trebuie indeplinita una din cele trei FORME ale principiului:


Forma 1: Dk, ...Dn conduce optim din Sk-1 in Sn oricare k metode INAINTE
Forma 2: D1, ...Dk conduce optim din S0 in Sk oricare k metode INAPOI
Forma 3: Ambele subsiruri sunt optime simultan  METODA MIXTA

Daca drumul cel mai scurt de la Bucuresti - Suceava trece prin Focsani, atunci portiunea Bucuresti-Focsani este si ea cea mai scurta.



n = 3

1
2 : 1 
    2

1 1 1
1 2
2 1
in total 3 moduri

1 1 1 1
1 1 2
1 2 1
2 1 1
2 2

in total 5 moduri

Sirul lui Fibonacci: 1,2,3,5,8

sir[3] = sir[2] + sir[1]

sir[n] = sir[n-1] + sir[n-2]


Problema se reduce la Sirul lui Fibonacci (care este o problema de dinamica)

DP = Dynamic Programming
*/


public class Fibonacci {
	

       //varianta 1: Recursiv naiv - O(2^n) timp , O(n)
       //nu folosi in productie sau la interviu fara sa mentionezi limitele

       public static int FibRecursiv(int n) {

              if(n <= 1) return n;              

              return FibRecursiv(n-1) + FibRecursiv(n-2);
       }

      //varianta 2: Memoizare - O(n) timp, O(n) space
       public static int FibMEMO(int n, int[] memo) {

              if(n <= 1) return n;

              if(memo[n] != 0) return memo[n];

              memo[ n ] = FibMEMO(n-1, memo) + FibMEMO(n-2, memo);

              return memo[ n ];

       }

       //varianta 3: DP iterativ - O(n)TIME, O(1) space
       public static int fibDP(int n) {

       	         if(n <= 1) return n;

       	         int prev = 0, curr = 1;

       	         for(int i = 2; i <=n ; ++i) {
       	         	  int next = prev + curr;
       	         	  prev = curr;
       	         	  curr = next;
       	         }

       	         return curr;
       }


       public static void main(String[] args) {

         int n = 10;

         System.out.println("Fibonacci pentru n = " + n);
         System.out.println("-------------------------");


         System.out.println("Recursiv NAIV = " + FibRecursiv(n));

         //varianta memoizare
         int[] memo = new int[n + 1];
         System.out.println("cu MEMOIZARE = " + FibMEMO(n, memo));


         //afisam primele 10 numere Fibonacci

         System.out.println("Primele 10 numere Fibonacci: ");

         for(int i = 0; i < 10; ++i) {

         	       System.out.print(fibDP(i));

         	       if(i < 9) System.out.print(", ");
         }

       }

}

//fib(10) = fib(9) + fib(8) = fib(8) + fib(7) + fib(7) + fib(6)....