Implementing A Fibonacci Optimal Algo In C++

Introduction

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting from 0 and 1. In this blog post, we'll discuss an optimal way to implement the Fibonacci algorithm in C++ using a technique called memoization.

Fibonacci Simple Recursion

A naïve way of implementing the Fibonacci algorithm is through recursion. Here is a simple C++ implementation:

#include <iostream>

int fib(int n) {
    if (n <= 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

int main() {
    int n = 10;
    std::cout << "Fibonacci number at position " << n << " is: " << fib(n) << std::endl;
    return 0;
}

While this implementation is effective for small values of n, it quickly becomes inefficient due to the exponential number of recursive calls leading to heavy time complexity (O(2^n)).

Optimal Fibonacci Algorithm using Memoization

To make the Fibonacci algorithm more efficient, we can use a technique called memoization. Memoization involves storing the results of expensive function calls and returning the cached result when the same inputs are used again.

Here is an example of a memoized Fibonacci algorithm in C++:

#include <iostream>
#include <vector>

int fib_memoization(int n, std::vector<int> &memo) {
    if (n <= 1)
        return n;

    // If the value is already calculated, return the cached result.
    if (memo[n] != -1)
        return memo[n];

    memo[n] = fib_memoization(n - 1, memo) + fib_memoization(n - 2, memo);
    return memo[n];
}

int fib(int n) {
    std::vector<int> memo(n + 1, -1);
    return fib_memoization(n, memo);
}

int main() {
    int n = 10;
    std::cout << "Fibonacci number at position " << n << " is: " << fib(n) << std::endl;
    return 0;
}

In this implementation, we use a std::vector<int> called memo to store the results of previous calculations. This decreases the number of recursive calls needed, resulting in a time complexity of O(n).

Conclusion

We have learned how to implement a memoized version of the Fibonacci algorithm in C++ to optimize its performance significantly. By storing the results of previous calculations, the algorithm now has a time complexity of O(n), which is a significant improvement over the naïve O(2^n) time complexity of the simple recursive implementation.