针对斐波那契数列算法进行详细介绍和优化,从最简单的递归方法到更高效的迭代、缓存、动态规划、公式推导和矩阵解法,最终达到了时间复杂度为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