posts - 195, comments - 34, trackbacks - 0, articles - 1

pku3233　矩阵相乘的反复平方法和矩阵等比和计算构造方法

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

  





只有注册用户登录后才能发表评论。
网站导航: