Dynamic Programming - Memoization Example using Fibonacci Sequence

fibonacci.cpp

#include <iostream>
#include <unordered_map>

/* --------------------------------------------------------------------------------------- */
/*	Fibonacci
	This code compares the runtime complexities of a memoized Fibonacci sequence calculation
	and a non-memoized Fibonacci sequence calculation.

	Commands to compile and run (on Windows):
	> g++ fibonacci.cpp -o fib
	> fib.exe
*/
/* --------------------------------------------------------------------------------------- */

// recursive fibonacci
// O(2^N) time, O(N) space
unsigned long long fib_recursive(int n)
{
	if (n <=2) return 1;
	return fib_recursive(n-1) + fib_recursive(n-2);
}

// memoization fibonacci
// O(N) time, O(N) space
unsigned long long fib(int n)
{
	// Pseudocode:
	// if n in memo, return memo(n)
	// do recursive implementation, but save results in memo
	
	// Implementation Note:
	// static memo - results will exist in memory for duration of program, 
	//	but will save time on subsequent fib calls (in fact, amoritized time in this program is actually O(1))
	// local memo -> helper that accepts memo reference will only use memory for
	//	duration of call, but subsequent calls will need to re-memo
	using FibonacciMemo = std::unordered_map<int, unsigned long long>;
	static FibonacciMemo memo;
	
	FibonacciMemo::iterator it = memo.find(n);
	if (it != memo.end()) return it->second;
	
	if (n <=2) return 1;
	memo.insert(std::make_pair(n, fib(n-1) + fib(n-2)));
	return memo[n];
}

int main()
{
	static const int sk_iterations = 50;
	
	std::cout << "Running Memoized Implementation (time complexity = O(N)):" << std::endl;
	for (int i = 1; i <= sk_iterations; i++)
	{
		std::cout << i << " : " << fib(i) << std::endl;
	}
	
	std::cout << "Running Non-Memoized Implementation (time complexity = O(2^N)):" << std::endl;
	for (int i = 1; i <= sk_iterations; i++)
	{
		std::cout << i << " : " << fib_recursive(i) << std::endl;
	}
	return 0;
}