锐客网

  1. 首页 > 睿知 > it技术 > >

python矩阵幂函数 python矩阵乘方( 五 )

IT技术复杂度


斐波那契数列和矩阵的关系推导我看到GoCalf Blog里写的一段非常清晰，特在此引用
这解法就是求矩阵的n-1次幂 。矩阵幂运算也能根据下面公式迭代二分加速
就是所谓的矩阵快速幂
Python里库很丰富 ， 大名鼎鼎的numpy就是一个有关矩阵的库 。这库是有优化的，算矩阵幂就不用个人再写什么矩阵快速幂函数了
用numpy库就能很简单的写出来
因为numpy没有大数支持 ， 大数运算还是要用GMP库
同上测用时
Total time: 0.042466秒
这幂运算是二分加速的，时间复杂度为O(log n)
对于固定阶矩阵相乘，乘的次数是个常数，也就是O(1) 。虽然这个常数比较大^_*
代入大数时间复杂度，总体复杂度也是O(n*(log n)^2)
这儿来解释下为何矩阵快速幂比二分递归解法时间常数大
我们再来仔细看看斐波那契数列的矩阵形式python矩阵幂函数：
会发现 z 和 y 必然相等，z 没必要再计算一遍 。
t = x - y ， 因此 t 也没必要再计算一遍 。
只需要计算矩阵第一列的那两个元素即可python矩阵幂函数：
矩阵快速幂中两个矩阵相乘实际可分解为8次两个大整数乘法，而二分递归中只需要3次两个大整数乘法 。所以二分递归时间常数小 。
未完待续……
Fibonacci数列高效解法大全及时间复杂度分析　连载【6】
关于python矩阵幂函数和python矩阵乘方的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

推荐阅读


上一篇：oracle数据库sql函数的使用，oracle sql语句大全实例教程

下一篇：百度新媒体如何做，百度新媒体如何做推广赚钱