posts - 195, comments - 34, trackbacks - 0, articles - 1
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为例:
int pow(int a, int m)
{
  
int y = 1;
  
int z = a;
  
while(m > 0)
  
{  
     
if( (n&1)==1 ) y = y*z;
     z 
= z * z;
     n 
= n >> 1;
  }

  
return y;
}
递归的可以不用变量Z,要简单些,但是要注意了递归的调用顺序和结果的存储。

  





只有注册用户登录后才能发表评论。


网站导航: