[일반] 질문.피보나치 행렬로 풀면 o(logn)이라잖아

[익명(223.62)]

근데 행렬곱하는 연산 자체가 o(n^3)언저리인데
그럼 o(logn)이 아니라 o(n^3) 아닌가요?

[익명(49.169)]

곱하는 행렬이 2*2 행렬이다 게이야

[익명(121.161)]

n이랑 2를 섞으면 어캄

[익명(84.157)]

행렬곱이 아니라 거듭제곱인데 행렬의 거듭제곱은 분할정복으로 할 수 있음

[익명(110.10)]

행렬의 크기가 k일때 O(k^3 logn)임. 그래서 유사한 문제인데 k가 크면 다른 방법 찾아야 되고

[익명(61.255)]

ㅋㅋ