Posted on 2009-11-02 21:26
小強摩羯座 閱讀(298)
評論(0) 編輯 收藏 所屬分類:
算法編程
pku3233：Given a
n ×
n matrix
A and a positive integer
k, find the sum
S =
A +
A2 +
A3 + … +
Ak.
分析：矩陣相乘O(n^3), 有k次，則復雜度為n^3*k。
使用矩陣技巧，構造：
B= | A A |
| O I |
則B的乘方的結果其右上會是S，其他三個不變。此時化成了矩陣乘方問題，此時可以使用反復平方法，這樣復雜度為(2n)^3*logk
反復平方法，迭代版的， 以整數a^m為例：
遞歸的可以不用變量Z，要簡單些，但是要注意了遞歸的調用順序和結果的存儲。
