행렬과 분할정복 기반의 피보나치 수 알고리즘

기존 피보나치의 수열을 구하는 알고리즘은 다음과 같다 int Fibonacci(int n) { if(n==0) return 0; if(n==1 || n==2) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } 하지만 이 알고리즘은 점점 재귀함수를 호출하는 횟수가 2배씩 늘어서시간복잡도가 이기 때문에 매우 비효율적이다.하지만 행렬과 분할정복 기법을 활용하면 수준으로 알고리즘을 개선할 수 있다. 우선 n번째 피보나치 수를 이라 하고 아래와 같은 2x2 정사각형 행렬을 만들 수 있다. 이 정사각행렬을 n번 제곱하면 다음과 같은 등식을 유도할 수 있다. 위의 행렬식을 이용해서 알고리즘을 만들면 의 알고리즘을 구현할 수 있지만 을 이용하면 좀 더 빠른 알고리즘을 설계할 ..

원문링크 : 행렬과 분할정복 기반의 피보나치 수 알고리즘