| 矩阵K次幂（fibonacci） | 您所在的位置：网站首页 › 矩阵的次幂怎么求 › 矩阵K次幂（fibonacci） |
矩阵K次幂（fibonacci）
|
Fibanacci 的复杂度O(logn)方式 记住【1,1】【1,0】还有n-1 fn等于返回数组的【0,0】 在矩阵相乘的时候也请记得我们需要用到一个temp 需要用到一个单位矩阵 fibnacci通过数学归纳法推出的矩阵快速幂公式
快速幂图解 根据上面的链接 在求幂的时候 暴力算法是不停的乘本身A 需要很多次的调用自己本身 乘很多次 时间复杂度高 但是所采用“分治法”将 1.多次幂运算乘以自己这个大问题分成若干的小问题 2.然后递归解决每一个小问题 3.合并子问题的解成大问题的解 如果n是偶数 An=A(n/2)*A^(n/2) n是奇数 An=A(a=(n-1)/2)*A^((n-1)/2)*A 快速幂又在上面基础上升级用二进制，我心里认为为什么要转二进制呢 ？ 就是最容易“分” 十进制都可以变为二进制嘛这样二进制的每一位就对应着一个子问题 -又最容易 “治” ，所有的子问题都可以继续递归 因为你2^15一定可以从2 ^12得来 就是说2的次幂是叠着乘的 后面的结果就是前面结果乘2获得的分治法让相乘次数减少 举例：* 这样A^4=AAAA 需要3次乘操作 现在A^4=A * A（第一次乘操作） x (AA) 只需要两次乘操作 A * *A 第一次乘操作然后结果作为一个整体 再次乘以自己 (A * A) *(A *A) 只需要2次乘法 44次相乘—》5次相乘  从最后一位看因为最后一位是2^0=1 所有的后面的子问题也都是从他相乘的来的 一定要从他开始的
看完是1还是0选择时候归入答案
|
什么要把10进制转为2进制呢？（对上下这两个图的解说，请参看） 首先二进制不是1就是0，上面我们把A^n拆分那到底会被拆分成那些子问题相乘 二进制一目了然 该位为1就会归并到答案中作为子问题合并 该位为0就不理会【本文地址】
公司简介
联系我们