[알고리즘] 피보나치 수열의 시간복잡도

 

 

기존 알고리즘

• O(2^n)
• 매 번 함수가 호출 될 때마다 또 두 번씩 호출 된다.

F(n, r) {
    if (n <= 0) return 0;
    else if (n == 1) return r[n] = 1;
    return r[n] = F(n-1, r) + F(n-2, r);
}

 

기존 알고리즘 + 메모이제이션

• O(n)
• 메모이제이션을 통해 n을 두 번 호출 안하게 된다.

F(n, r) {
    if (n <= 0) return 0;
    else if (n == 1) return r[n] = 1;
    ⭐ else if (r[n] > 0) return r[n]; ⭐
    return r[n] = F(n-1, r) + F(n-2, r);
}

 

변형된 피보나치 수열 풀이코드

• O(n2^n)으로 계산은 틀렸다.
  
  • 2^n을 n번 반복하는 것으로 때문에 착각할 수 있다.
• allF은 1부터 n까지의 모든 피보나치 수를 계산하고 출력  
  
  • F(1): O(2^1)
  • F(2): O(2^2)
  • F(3): O(2^3)
  • ...
  • F(n): O(2^n)

• O(2^1 + 2^2 + 2^3 + ... + 2^n-1 + 2^n)
  = 2^n - 2 + 2^n
  = 2 * 2^n - 2
  = 2^n (상수는 모두 제외)

allF(n) {
    for (i=1 to n) print F(i);
}
F(n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    return F(n-1) + F(n-2);
}

 

---

메모이제이션

F(5, r) 풀기

• ⭐ 배열의 초기 모든 값은 0 이다. ⭐

int r[6] = {0, 0, 0, 0, 0, 0}; // 초기화된 배열
int result = F(5, r);          // 피보나치 수열의 5번째 값을 계산

 

1. 5는 0보다 크기 때문에 처음 if문은 지나간다.
2. 5는 1과 같지 않기 때문에 처음 else-if문을 지나간다.
3. r[5]는 0이기 때문에 두 번째 else-if문을 지나간다.
   => 처음 배열의 모든 값은 0이다.
4. 그럼 return으로 F(4, r) + F(3, r)을 반환한다.

이렇게 계속 반복하면서 F(5), F(4), F(3), F(2), F(1), F(0)을 만나는 순간 !!

   => 두 갈래로 나누면서 계속 내려가겠지만 한쪽에서 분명 F(1)과 F(0)을 만나게 된다.

 

역으로 값을 하나씩 더하면서 배열의 값을 수정한다.
  => F(0, r)=0 , F(1, r)=1, F(2, r)=1, F(3, r)=2, ...

  => int r[6] = {0, 1, 1, 2 .... }

 

즉, 한 쪽에서 계산하고 배열에 값을 저장해 놓으면

다른 한 쪽에서는 다시 나눌 필요없이 배열에서 값을 가져와서 더하면 끝!

  => " 다시 나눌 필요없이"는  F(n-1, r)  + F(n-2, r)를 의미

  => 우리는 해당 F(n-1, r) 의 값을 배열에서 바로 알 수 있다.

 

따라서 O(2^n)이 아닌 O(n) 복잡도로 계산이 끝난다.

 

참고사이트

https://www.youtube.com/watch?v=VcCkPrGaKrs