用矩阵幂求解线性递推序列

用矩阵幂求解线性递推序列
在上一篇文章中我们探讨了如何快速求解幂运算的方法,并且最终给出了一个时间复杂度为O(logn)的算法,那么在这一片文章中,我想说一说快速幂运算的一个应用,也就是利用矩阵的快速幂运算求解线性递推序列。 首先我们来了解下什么是线性递推序列,在这里给大家看一个大家一定很熟悉例子,那就是斐波那契数列,它的递推公式是: 从上面这个方程中我们可以看到很明显的递推关系,实际上我们在做运算的时候,如果一步一步的按照递推式计算,将会消耗大量的时间,于是我们求助于其它的方式。 首先,对于一般的k阶线性递推函数y,应当有这样的形式: 若对于这个递推函数,如果对所有不小于k的n有: 直观来看,这个递推函数应该是长成这个样子的: 当给定了从X(0) ~ X(k – 1) 的k个初始值的时候,我们就能利用这个递推公式计算出所整个序列。那么解决问题的关键就落在了递推函数f的身上。 观察递推函数f的形式,我们发现它可以用两个向量乘积的形式来表达: 为了使用这个函数计算的递推序列能够方便的进入下次的跌打运...

快速幂运算

快速幂运算
最近看到的一些题里有利用快速矩阵幂来求快速解递归函数(比如Fibonacci数列),在很久之前看和RSA算法里也涉及到了快速求幂的算法,所以今天就想一块来介绍一下。 在介绍开始之前,先对本文的算法做一个声明,下文所提到的幂运算的指数n,满足条件n >= 0,这一点非常重要。 首先幂运算,大家其实都很好理解,其实就是: 无非就是把一个数自乘n次,所以我们通常计算数字的幂的算法就是: (代码1) [crayon-5bc6e97e03203646540109/] 这个算法很简单,其复杂度是O(n)的,一般来说,这样的复杂度并不会使我们困惑,但是一般应用幂运算的地方,指数都会非常非常的大,比如1 000 000 000这个级别的,这时候我们会遇到两个问题,第一个就是我们不能再用int来存储整数,必须用高精度整数类型来进行存储,另一个就是在指数是如此变态的数量级之下,我们的计算量会骤然上升,结果也会异常惊人的大。 快速幂算法就是为了解决这个问题而发明的,其实它本身很简单,就是利用二分法,在具体介绍...