针对斐波那契数列算法进行详细介绍和优化，从最简单的递归方法到更高效的迭代、缓存、动态规划、公式推导和矩阵解法，最终达到了时间复杂度为O(logn)的快速幂矩阵解法来感受算法的神奇之处，最后可以看到如何实现在输入n=2100000000（21亿）时仅耗时0.02毫秒的最佳效果。
一、回顾斐波那契数列
斐波那契数列（Fibonacci sequence）是一种非常经典的数学序列，其特点是每个数字是前两个数字之和，起始于0和1。也就是说，数列的第三个数是前两个数的和，第四个数是第二个数和第三个数的和，以此类推。斐波那契数列的前几项是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
这个数列最早是意大利数学家斐波那契（Fibonacci）在其《算盘书》（1202年）中引入的，用来描述兔子繁殖的理想化情况。假设一对刚出生的兔子一年后成熟并能生育，且从第二年开始每年产下一对新兔子，不考虑其他因素的影响。这个问题导致了斐波那契数列的产生，兔子的对数就对应了斐波那契数列的每一项。
那通过算法实现求第n个斐波那契数的具体数值，让我们感受下算法的不断优化和极致表现。
二、矩阵解法+快速幂解法分析
基本思想是利用矩阵乘法的性质，将斐波那契数列的递推关系表示为矩阵形式，然后通过快速幂算法来快速计算矩阵的高次幂，从而得到斐波那契数列的第n项的值。
三、代码展示
package org.zyf.javabasic.algorithm;
/**
* @program: zyfboot-javabasic
* @description: 使用矩阵解法结合快速幂
* @author: zhangyanfeng
* @create: 2024-04-25 01:06
**/
public class MatrixFibonacciWithFastPower {
private static final long[][] INIT_MATRIX = {{1, 1}, {1, 0}};
private static final long[][] UNIT_MATRIX = {{1, 0}, {0, 1}};
public static long getFibonacciByMatrixAndFastPower(int index) {
// 检查索引的有效性
if (index <= 0) {
throw new IllegalArgumentException("Index must be a positive integer");
}
// 边界情况处理
if (index == 1 || index == 2) {
return 1;
}
// 初始结果为单位矩阵
long[][] result = UNIT_MATRIX;
long[][] temp = INIT_MATRIX;
int m = index - 2;
// 利用快速幂算法计算矩阵的高次幂
while (m != 0) {
if ((m & 1) == 1) {
result = matrixMultiply(temp, result);
}
temp = matrixMultiply(temp, temp);
m >>= 1;
}
// 结果矩阵的第一个元素即为斐波那契数列的第n项的值
return result[0][0];
}
// 矩阵乘法
private static long[][] matrixMultiply(long[][] a, long[][] b) {
long[][] result = new long[2][2];
result[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
result[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
result[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
result[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
return result;
}
public static void main(String[] args) {
// 计算第100000项的斐波那契数
long startTime1 = System.nanoTime();
long fibonacci100000 = MatrixFibonacciWithFastPower.getFibonacciByMatrixAndFastPower(100000);
long endTime1 = System.nanoTime();
double elapsedTime1 = (endTime1 - startTime1) / 1_000_000.0; // 转换为毫秒
System.out.println("Fibonacci(100000) = " + fibonacci100000);
System.out.println("耗时：" + elapsedTime1 + "毫秒");
// 计算第2100000000项的斐波那契数
long startTime2 = System.nanoTime();
long fibonacci2100000000 = MatrixFibonacciWithFastPower.getFibonacciByMatrixAndFastPower(2100000000);
long endTime2 = System.nanoTime();
double elapsedTime2 = (endTime2 - startTime2) / 1_000_000.0; // 转换为毫秒
System.out.println("Fibonacci(2100000000) = " + fibonacci2100000000);
System.out.println("耗时：" + elapsedTime2 + "毫秒");
}
}四、性能分析
时间复杂度分析：计算第n项斐波那契数需要进行快速幂运算，时间复杂度为O(log n)。这是因为快速幂算法的时间复杂度为O(log n)，在算法中只需进行log n次乘法运算。在快速幂运算中，每次矩阵相乘的时间复杂度为O(1)。因此，总的时间复杂度为O(log n)。
空间复杂度分析：算法中使用的空间主要由两个矩阵所占用的空间决定。这两个矩阵分别是初始矩阵和结果矩阵，都是固定大小的2x2矩阵。因此，空间复杂度为O(1)，即常数级别的空间复杂度。
实际运行发现当n为10万时耗时0.013125毫秒，n为21亿时耗时0.022042毫秒。
矩阵解法结合快速幂的斐波那契数列算法具有优秀的时间复杂度O(log n)和空间复杂度O(1)，适用于需要高效计算大数值斐波那契数列的场景。
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/xiaofeng10330111/article/details/138143503