kimsy96   2년 전

어찌어찌 O(N) 까지는 줄 일 수 있겠지만..

그 이상으로 시간복잡도를 줄여야 풀리는 문제인데 아이디어가 안떠오르네요

조금 도와주셨으면 합니다

jh05013   2년 전

피보나치 수를 O(logN)만에 구하는 것과 같은 방법으로 선형 점화식의 N번째 항을 O(logN)만에 구할 수 있습니다.

kimsy96   2년 전

오 유명한 알고리즘인가요..? 음 우선 제가 피보나치 수를 O(NlgN)만에 구하는 알고리즘을 몰라서.. 가르쳐 주시면 둘다 한번 공부해보겠습니다

jh05013   2년 전

n번째 피보나치 수를 Fn이라고 할 때, 다음이 성립합니다.

fea3b36a-4019-4193-8cf9-e911673ab92e

맨 오른쪽의 Fn-1, Fn-2를 다시 위 식에 넣고, 이를 반복하면

245b02bc-07a0-4667-92b0-effa19d72939

이므로 행렬의 거듭제곱 모듈로 m을 O(logN)만에 계산하면 N번째 피보나치 수 모듈로 m을 알 수 있습니다.

kimsy96   2년 전

아 저건 가지고 있는 책 어디서 본 거 같네요. 근데 저 식을 3차 정수방정식에 어떻게 활용할지 감이 잘 안잡히지만..

 조금 더 고민해보겠습니다 

댓글을 작성하려면 로그인해야 합니다.