Posted on 2009-11-02 21:26
小强摩羯座 阅读(264)
评论(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,要简单些,但是要注意了递归的调用顺序和结果的存储。