피보나치 수열의 시간복잡도는 왜 θ(1.618의 N제곱)일까

# 최근에 나동빈 저자의 "이것이 취업을 위한 코딩테스트다 with 파이썬"를 보다가 궁금증이 생겼다.

   예전에 문제풀 때는 일단 실력을 끌어 올리는 것에 중점을 둬서 그냥 외우고 넘어갔지만,

   다시 한번 복습하는 차원에서 여유롭게 읽어보니 깊게 생각해 봐도 될 부분들이 많았다.

 

# 다이나믹 프로그래밍 Chapter에서 단골손님으로 나오는 '피보나치 수열'에서 피보나치 수열의

   시간복잡도가 정확히 따지면 θ(1.618...^N)이라는 것이다.

   일반적으로 피보나치 수열의 시간복잡도는 세타 표기법으로 표시하지 않고 빅오 표기법으로

    O(2^N)으로 표시를 한다.

 

# 궁금해서 인터넷을 찾아보니 피보나치 수열의 일반항 F_n을 다음과 같이 나타낼 수 있다.

출처: https://thewiki.kr/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4#fn-2

# 증명은 아래와 같은데, 증명까지 외울 필요는 없고 그냥 왜 이런 점화식이 나오는지 이해하고

   넘어가면 될 것 같다.

출처: https://thewiki.kr/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4#fn-2

 

# (1 + √5) / 2 이 우리가 흔히 볼 수 있는 황금비(1.618...)이므로 Fn을 세타 표기법으로 나타내면

   점화식에 의해서 θ(1.618...^N)이 된다.

   (문제풀이 할때는 최악의 경우를 보통 따지므로 O(2^N)으로 생각하고 풀면 된다.