피보나치 공식1 분할 정복을 이용한 거듭제곱 최적화 아마 다음은 이미 알고 있을 것이다. 예를들어 거듭제곱되는 수치가 짝수일 때와 홀수일 때를 예로들면 다음과 같다. A^4 = (A^2)^2 (짝수일때) A^5 = A * A^4 = A * (A^2)^2 (홀수일때) 만약 A^8이 있다면 원래는 A*A*A*A*A*A*A*A 으로 곱셈 연산을 7번 해야 하지만, A^8을 ((A^2)^2)^2 으로 변경하면 A*A=A', A'^2=A'' 이라 할 시 최종적으로 A'을 구하는데에 A*A로 곱셉 한번, A''=A'*A'을 구하는데도 마찬가지로 곱셈 한번, 최종적으로 A''*A''을 구하는데 곱셈 한 번이 들어간다. 즉 7번의 연산이 3번의 연산으로 줄어든다! 즉, 거듭제곱을 위와 같이 계산한다면 원래 N번의 연산이 O(logN)으로 줄어든다. 여기서 분할정복을 활.. 2022. 4. 5. 이전 1 다음
