快速幂+矩阵优化斐波那契数列(超详细教程)前言一、快速幂二、矩阵优化斐波那契数列三、全部实现代码
文章目录前言一、快速幂二、矩阵优化斐波那契数列1.矩阵相关知识2.斐波那契数列用矩阵表示3.O(log2n)的斐波那契数列总结前言我们首先讲解快速幂,然后利用快速幂优化矩阵相乘,将O(n)算法变为O(log2n),紧接着我们用矩阵,优化斐波那契数列!一、快速幂通常我们算一个数(a)的n次幂,我们需要计算n次,也就是n个a相乘,这样难免太过缓慢,于是有了快速幂,即不需要n次操作就可以算出!举例:计算A的9次幂通过上述操作想必大家明白,快速幂的思想也就是二分的思想!代码实现:#include
