[자료구조] 피보나치 수열

시간 복잡도 : O(2^n)

// C# 
Console.WriteLine($"{F1(30)}");


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

위 코드는 비효울적이다...

 

시간 복잡도 : O(n)

// C#

Dictionary<int, int> dic = new Dictionary<int, int>();
Console.WriteLine($"{F2(50, dic)}");

int F2(int n, Dictionary<int, int> numbers)
{
    int v;
    if (n <= 0) return 0;
    else if(n == 1) return 1;
    else if (numbers.TryGetValue(n, out v)) return v;
    else return numbers[n] = F2(n - 1, numbers) + F2(n - 2, numbers);
}

딕셔너리로 해당 n의 키값으로 저장하고 나중에 또 다시 재귀호출로 인해서 계산하지 않고 

바로 값을 반환하여 중복 호출은 하지않게 만들어주는 코드다.

해당 값을 어디에 기억하는 장소를 만든것이다.