Posted on 2009-11-02 21:26
小強(qiáng)摩羯座 閱讀(303)
評論(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次，則復(fù)雜度為n^3*k。
使用矩陣技巧，構(gòu)造：
B= | A A |
| O I |
則B的乘方的結(jié)果其右上會是S，其他三個不變。此時化成了矩陣乘方問題，此時可以使用反復(fù)平方法，這樣復(fù)雜度為(2n)^3*logk
反復(fù)平方法，迭代版的， 以整數(shù)a^m為例：
遞歸的可以不用變量Z，要簡單些，但是要注意了遞歸的調(diào)用順序和結(jié)果的存儲。
