피보나치 3가지 방법

#include<iostream>
using namespace std;
int f[10] = {}; // 전역변수
int fibo(int n) // 반복문을 이용한 피보나치
{
    int s = 0, f0=0, f1=1;
    if (n <= 1)
        return n;
    for (int i = 2; i <= n; i++)
    {
        s = f0 + f1;
        f0 = f1;
        f1 = s;
    }
    return s;
}
 
int rfibo(int n) //재귀를 이용한 피보나치
{
    if (n <= 1) return n;
    return rfibo(n - 2) + rfibo(n - 1);
}
int mfibo(int n) // 전역변수를 이용한 피보나치 암기
{
    
    if (n <= 1) 
    {
        f[n] = n;
        return n;
    }
    else
    {
        if (f[n - 2] == -1) 
            f[n - 2] = mfibo(n - 2);
        if (f[n - 1] == -1)
            f[n - 1] = mfibo(n - 1);
        f[n] = f[n - 2] + f[n - 1];
        return f[n];
    }
    
}
int main()
{
    for (int i = 0; i < 10; i++) // f배열의 값을 다 -1로 넣
    {
        f[i] = -1;
    }
    cout << fibo(6);
    cout << rfibo(6);
    cout << mfibo(6);
    return 0;
}

첫번째 반복문을 이용한 방법은 O(n)

두번쨰 재귀를 이용한 방법은 O(n^2)

이 방법은 재귀로 계속 돌아가기 때문에 O(n^2)만큼 걸림

세번째 배열로 저장해서 사용한 방법은 O(n) 

이 방법은 피보나치수가 구해져있으면 메모리에 저장해두고 안구해져있으면 메모리에 저장되어있는것을 다시 사용해서 O(n)만큼 걸린다.