首页 > 编程语言 >秒懂斐波那契:算法优化实现21亿级速度突破

秒懂斐波那契:算法优化实现21亿级速度突破

时间:2024-08-04 15:24:08浏览次数:12  
标签:懂斐波 21 复杂度 矩阵 long 斐波 亿级 那契 数列

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

标签:懂斐波,21,复杂度,矩阵,long,斐波,亿级,那契,数列
From: https://blog.csdn.net/m0_74022416/article/details/140906534

相关文章

  • 探秘斐波那契数列:如何在0.02毫秒内计算21亿
    针对斐波那契数列算法进行详细介绍和优化,从最简单的递归方法到更高效的迭代、缓存、动态规划、公式推导和矩阵解法,最终达到了时间复杂度为O(logn)的快速幂矩阵解法来感受算法的神奇之处,最后可以看到如何实现在输入n=2100000000(21亿)时仅耗时0.02毫秒的最佳效果。一、回顾斐波......
  • 极限性能:21亿斐波那契数列在0.02毫秒内计算完成
    针对斐波那契数列算法进行详细介绍和优化,从最简单的递归方法到更高效的迭代、缓存、动态规划、公式推导和矩阵解法,最终达到了时间复杂度为O(logn)的快速幂矩阵解法来感受算法的神奇之处,最后可以看到如何实现在输入n=2100000000(21亿)时仅耗时0.02毫秒的最佳效果。一、回顾斐波......
  • 没闲着系列 21
    离上个20记录已经3个月了。这3个月我算体会到了什么是欠缺项目管理导致的项目失败。当然,有一部分我认为项目是没有失败的,但有一部分也是个人原因,但不多。算了,不去想之前的糟心事,讲一讲TaskSaas近期更新了什么吧。首先还是关于迭代需求,现在不创建迭代不允许新增需求了。然后细......
  • 算法力扣刷题记录 六十四【216.组合总和III】
    前言回溯第二篇。回顾:上一篇学了回溯的基础知识和模版;组合练习题一应用了一次模版。本文继续组合问题练习:记录六十四【216.组合总和III】。一、题目阅读找出所有相加之和为n的k个数的组合,且满足下列条件:只使用数字1到9每个数字最多使用一次返回所有可能的有效......
  • ECMAScript 12 (ES12, ES2021) 新特性
    还是大剑师兰特:曾是美国某知名大学计算机专业研究生,现为航空航海领域高级前端工程师;CSDN知名博主,GIS领域优质创作者,深耕openlayers、leaflet、mapbox、cesium,canvas,webgl,echarts等技术开发,欢迎加底部微信(gis-dajianshi),一起交流。No.内容链接1Openlayers【入门教程】-......
  • leetcode数论(2521. 数组乘积中的不同质因数数目)
    前言经过前期的基础训练以及部分实战练习,粗略掌握了各种题型的解题思路。现阶段开始专项练习。数论包含最大公约数(>=2个数)、最大公约数性质、最小公倍数、区间范围质因素计数(最下间隔)、质因素分解、判断质数、平方根、立方根、互质、同余等等。描述给你一个正整数数组......
  • leetcode 021:删除链表的倒数第 N 个结点
    LCR021.删除链表的倒数第N个结点给定一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。示例1:输入:head=[1,2,3,4,5],n=2输出:[1,2,3,5]示例2:输入:head=[1],n=1输出:[]示例3:输入:head=[1,2],n=1输出:[1]structListNode*removeNthF......
  • K12182 挂号系统
    题目描述科丁医院想请科丁博士帮忙编写一个挂号系统。具体是这样的,最近来医院看病的人越来越多了,因此很多人要排队,只有当空闲时放一批病人看病。但医院的排队不同其他排队,因为多数情况下,需要病情严重的人优先看病,所以希望科丁博士设计系统时,以病情的严重情况作为优先级,判断接......
  • leetcode 2181.合并零之间的结点
    1.题目要求:/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*mergeNodes(structListNode*head){structListNode*cur=head;intcount=0;//1.遍历结......
  • leetcode 2181.合并零之间的结点
    1.题目要求:/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*mergeNodes(structListNode*head){structListNode*cur=head;intcount=0;//1.遍历结......