Analiza Complexitatii pornind de la complexitate exponentiala pana la complexitate constanta. Adaugare functie lambda

fibonacci.cpp

//Fibonacci Sequence 
//0,1,1,2,3,5,8,13,21, 34,.....infinit
//Algoritmul Naiv 

//Big O Notation: O(2^n)

/*

long long fib_exponential(int n) {

    if(n <= 1) return 1;

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


               f(5) = f(4) + f(3) = f(3) + f(2) + f(2) + f(1) = f(2) + f(1);


                        f(5)


                    f(4)    f(3)         


                f(3) f(2)  f(2) f(1)  


              f(2) f(1) f(1) (0) 1 

              n = 1000


    Complexitate O(n)  Memoization TOP - DOWN (Hash Map)


    unordered_map<int, long long> memo;


    long long fib_memo(int n) {
	
	         if(n <= 1) return n;

	         if(memo.count(n)) return memo[n];

	         memo[n] = fib_memo(n-1) + fib_memo(n-2)

	         return memo[n];
    }
*/


//Complexitate O(n)  Memoization TOP - DOWN (Hash Map)
#include<iostream>
#include<unordered_map>
#include <vector>
#include <functional>

using namespace std;

long long fib_exponential(int n) {

    if(n <= 2) return 1;

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


unordered_map<int, long long> memo;


    long long fib_memo(int n) {
	
	         if(n <= 1) return n;

	         if(memo.count(n)) return memo[ n ];

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

	         return memo[n];
    }

    //Memoization Top-Down (Vector) O(n) complexitate liniara
    
    ///
    //0,1,1,2,3,5,8,13.....
    //     <<<<<<<<<<---- (top)
    
    long long fib_memo_vec(int n) {

          vector<long long> dp(n + 1, -1);

    	  function<long long(int)> solve = [&](int k) -> long long {

                   if(k <= 1) return k;

                   if(dp[k] != -1) return dp[k];

                   return dp[k] = solve(k-1) + solve(k-2);      
    	  };

    	  return solve(n);
    }

    //0,1,1,2,3,5,8,13.....
    //-->>>>>>>>>>>>>
    //Complexitate O(n) Bottom - UP Dynamic Programming
    long long fib_dp(int n) {

         if(n <= 1) return n;

         long long prev2 = 0, prev1 = 1;

         for(int i = 2; i <= n; ++i) {

         	long long curr = prev1 + prev2;

         	prev2 = prev1;
         	prev1 = curr;
         } 

         return prev1;
    }


    auto salut = []() {

    	 cout<<"hello" <<endl;
    };

    auto aduna = [](int a, int b) -> int {

    	return a + b;
    };

    //Complexitate Constanta O(1) - forumula lui Binet
    long long fib_Binet(int n) {

    	   const double SQRT5 = sqrt(5.0);
    	   const double PHI = (1.0 + SQRT5) / 2.0;
    	   const double PSI = (1.0 - SQRT5) / 2.0;

    	   return long long round((pow(PHI, n)) - pow(PSI,n)) / SQRT5;
    }


    //1,2,3,5,8
int main(int argc, char const *argv[])
{

	cout<<fib_exponential(7)<<endl;  

    //1,1,2,3,5,8,13
	cout<<fib_memo( 7 )<<endl;

    cout<<fib_memo_vec( 7 );

    salut();

    cout<<aduna(1,1)<<endl;


    int x = 10;

    auto adaugaX = [&](int a) {
    	
    	return a + x; //x este capturat prin referinta
    };


    cout<<adaugaX(10);

    /*
     [&] - captureaza totul print REFERINTA
     [=] - captureaza prin copiere
     [] - nu captureaza nimic
     [&a] - captureaza doar a prin referinta

     Semnatura lambda-ului este urmatoarea:

     (int k) -> long long

     (int k) - parametru primit

     -> long long - tipul returnat explicit (necesar cand compilatorul nu-l poate deduce singur mai ales prin recursie)
    */
	
	return 0;
}