用斐波那契数列感受算法的神奇（21亿耗时0.2毫秒）

news/2024/5/18 17:38:46

目录

一、回顾斐波那契数列

二、简单递归方法

（一）解决思路

（二）代码展示

（三）性能分析

三、采用递归+HashMap缓存

（一）解决思路

（二）代码展示

（三）性能分析

四、采用递归+数组缓存（记忆化搜索）

（一）解法思路

（二）代码展示

（三）性能分析

五、数组缓存+顺序迭代

（一）解法思路

（二）代码展示

（三）性能分析

六、取消缓存直接采用迭代优化

（一）解法思路

（二）代码展示

（三）性能分析

七、用初等代数推导公式解法

（一）解法分析

（二）代码展示

（三）性能分析

八、矩阵解法

（一）解法分析

（二）代码展示

（三）性能分析

九、矩阵解法+快速幂

（一）解法分析

（二）代码展示

（三）性能分析

十、最优解分析

针对斐波那契数列算法进行详细介绍和优化，从最简单的递归方法到更高效的迭代、缓存、动态规划、公式推导和矩阵解法，最终达到了时间复杂度为O(logn)的快速幂矩阵解法来感受算法的神奇之处，最后可以看到如何实现在输入n=2100000000（21亿）时仅耗时0.2毫秒的最佳效果。

一、回顾斐波那契数列

斐波那契数列（Fibonacci sequence）是一种非常经典的数学序列，其特点是每个数字是前两个数字之和，起始于0和1。也就是说，数列的第三个数是前两个数的和，第四个数是第二个数和第三个数的和，以此类推。斐波那契数列的前几项是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

这个数列最早是意大利数学家斐波那契（Fibonacci）在其《算盘书》（1202年）中引入的，用来描述兔子繁殖的理想化情况。假设一对刚出生的兔子一年后成熟并能生育，且从第二年开始每年产下一对新兔子，不考虑其他因素的影响。这个问题导致了斐波那契数列的产生，兔子的对数就对应了斐波那契数列的每一项。

那通过算法实现求第n个斐波那契数的具体数值，让我们感受下算法的不断优化和极致表现。

二、简单递归方法

（一）解决思路

递归的思路是将一个大问题拆解成更小的相似问题来解决。

对于斐波那契数列，我们首先要考虑斐波那契数列的基本情况，即当n为0或1时，斐波那契数列的值分别为0和1。这是递归的结束条件。

接下来，我们需要定义斐波那契数列的递归关系。根据定义，斐波那契数列的第n个数是前两个数之和，即F(n) = F(n-1) + F(n-2)。因此，我们可以将问题拆解成求解F(n-1)和F(n-2)的问题。

在求解F(n)之前，我们需要先求解F(n-1)和F(n-2)。为了求解这两个问题，我们可以再次调用相同的函数，直到达到基本情况。

在递归调用的过程中，当n为0或1时，递归将会终止。这是因为这两个值是斐波那契数列的基本情况，不需要再进行递归调用。

但需要注意的是，递归方法在求解大规模斐波那契数列时效率非常低，因为存在大量的重复计算。因此，虽然递归是一种常用的解决问题的方法，但在实际应用中需要谨慎使用，尤其是在处理大规模数据时。

（二）代码展示

package org.zyf.javabasic.algorithm;/*** @program: zyfboot-javabasic* @description: Fibonacci算法* @author: zhangyanfeng* @create: 2024-04-24 08:22**/
public class RecursiveFibonacci {/*** 当传入n=50时，递归方法在电脑上耗时高达35.549秒。*/public static int fibonacciRecursive(int n) {// 边界条件：当n为0或1时，斐波那契数列的值分别为0和1if (n == 0) {return 0;} else if (n == 1) {return 1;}// 递归调用：求解F(n-1)和F(n-2)，然后返回它们的和else {return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);}}public static void main(String[] args) {System.out.println("简单递归方法验证");// 验证斐波那契数列前几项的正确性// 测试不同n值下的性能for (int n = 0; n <= 50; n += 5) {long startTime = System.nanoTime();int result = fibonacciRecursive(n);long endTime = System.nanoTime();long duration = (endTime - startTime) / 1000000; // 毫秒System.out.println("Fibonacci(" + n + ") = " + result + ", Time: " + duration + "ms");}}
}

（三）性能分析

  1. 时间复杂度：时间复杂度可以近似为O(2^n)，因为每次调用都会分解为两个递归调用，直到达到基本情况。随着n的增加，计算时间呈指数级增长。

  2. 空间复杂度：对于斐波那契数列的递归方法，空间复杂度可以近似为O(n)，因为递归调用栈的深度最多为n。

实际性能验证：当传入n=50时，耗时为37021毫秒，即37.021秒。因此，我们可以合理推测，当传入n=100时，耗时可能会更长，但具体的时间取决于计算机性能和实现细节。（前提：我电脑的配置较高，如果电脑不给力，可能时间更长）

三、采用递归+HashMap缓存

（一）解决思路

采用递归+HashMap缓存的优化方法，也称为Memoization，是一种动态规划的思想。

首先使用递归来求解斐波那契数列的时候，我们知道递归是一种自顶向下的方法，从原始问题开始，不断地将其分解为更小的子问题，直到达到基本情况。

所以在递归的过程中，我们会遇到大量的重复计算。例如，在计算F(5)时，可能会需要计算F(4)和F(3)，而在计算F(4)时又会需要计算F(3)和F(2)，以此类推。

为了避免重复计算，我们可以使用HashMap来缓存已经计算过的结果。这样，当我们需要计算某个斐波那契数时，首先检查HashMap中是否已经存在该值，如果存在则直接返回缓存的结果，否则进行计算并将结果存入HashMap中。

将递归方法转化为自顶向下的动态规划。通过缓存已经计算过的结果避免了重复计算，大大提高了效率。

（二）代码展示

package org.zyf.javabasic.algorithm;import com.google.common.collect.Maps;import java.math.BigInteger;
import java.util.HashMap;/*** @program: zyfboot-javabasic* @description: 采用递归+HashMap缓存* @author: zhangyanfeng* @create: 2024-04-24 08:43**/
public class MemoizationFibonacci {private static HashMap<Integer, BigInteger> memoization = Maps.newHashMap();public static BigInteger fibonacciWithMemoization(int n) {if (n <= 1) {return BigInteger.valueOf(n);}// 如果HashMap中已经有了斐波那契数列的第n项的值，则直接返回缓存结果if (memoization.containsKey(n)) {return memoization.get(n);}// 如果HashMap中没有斐波那契数列的第n项的值，则进行递归计算，并将结果存入HashMap中BigInteger result = fibonacciWithMemoization(n - 1).add(fibonacciWithMemoization(n - 2));memoization.put(n, result);return result;}public static void main(String[] args) {// 验证斐波那契数列前几项的正确性for (int i = 0; i < 10; i++) {System.out.println("Fibonacci(" + i + ") = " + fibonacciWithMemoization(i));}long startTime = System.currentTimeMillis();BigInteger result = fibonacciWithMemoization(8000);long endTime = System.currentTimeMillis();long elapsedTime = endTime - startTime;System.out.println("Fibonacci( 8000 ) = " + result);System.out.println("程序运行时间：" + elapsedTime + " 毫秒");long startTime1 = System.currentTimeMillis();BigInteger result1 = fibonacciWithMemoization(10000);long endTime1 = System.currentTimeMillis();long elapsedTime1 = endTime1 - startTime1;System.out.println("Fibonacci(10000) = " + result1);System.out.println("程序运行时间：" + elapsedTime1 + " 毫秒");long startTime2 = System.currentTimeMillis();BigInteger result2 = fibonacciWithMemoization(19000);long endTime2 = System.currentTimeMillis();long elapsedTime2 = endTime2 - startTime2;System.out.println("Fibonacci(19000) = " + result1);System.out.println("程序运行时间：" + elapsedTime2 + " 毫秒");}
}

（三）性能分析

  1. 时间复杂度：递归+HashMap缓存方法通过缓存已经计算过的结果，避免了重复计算，因此实际的递归调用次数会显著减少。时间复杂度是优化后的O(n)，其中n是斐波那契数列的索引。

  2. 空间复杂度：使用HashMap来存储已经计算过的斐波那契数列的值。因此空间复杂度主要取决于递归调用的深度，空间复杂度是O(n)。

实际运行发现当n为8000耗时6 毫秒，n为10000时耗时1毫秒，性能变好了，但当n为18000的时候耗时4毫秒性能上又变差了，然后n为18400时出现StackOverflowError。性能上破不了18400。

递归的调用栈是有限的，因此当递归层级过深时会导致 java.lang.StackOverflowError。在斐波那契数列问题中，使用递归求解时，随着n的增大，递归调用的层级也会线性增长，因此当n较大时，容易出现栈溢出的情况。

为了解决这个问题，可以考虑使用迭代的方式来计算斐波那契数列，而不是递归。迭代的方式不会涉及到递归调用，因此不会出现栈溢出的情况，适用于大规模的计算。

四、采用递归+数组缓存（记忆化搜索）

（一）解法思路

采用递归+数组缓存的方法是一种记忆化搜索（Memoization）或者自顶向下的动态规划的经典应用。核心思想是通过递归的方式计算斐波那契数列的值，并利用数组来缓存已经计算过的值，避免重复计算，从而提高效率。

首先定义一个递归函数，用来计算斐波那契数列的第n项的值。在递归函数中，需要处理两种情况：

  • 基本情况：当n为0或1时，直接返回n作为结果。
  • 递归情况：对于其他的n，递归地计算斐波那契数列的第n-1项和第n-2项的值，然后将它们相加作为结果返回。

在递归函数中，使用一个数组来缓存已经计算过的斐波那契数列的值。每次计算新的斐波那契数列的值之前，先检查数组中是否已经存在了对应项的值。如果存在，则直接返回缓存结果，而不进行重复计算；如果不存在，则进行递归计算，并将结果存入数组中。在递归函数的最后，返回计算得到的斐波那契数列的第n项的值。

（二）代码展示

package org.zyf.javabasic.algorithm;import java.math.BigInteger;/*** @program: zyfboot-javabasic* @description: 采用递归+数组缓存的方法来计算斐波那契数列* @author: zhangyanfeng* @create: 2024-04-24 23:22**/
public class MemoizationFibonacciForArray {private static BigInteger[] memoization;public static BigInteger fibonacciWithMemoization(int n) {memoization = new BigInteger[n + 1]; // 初始化缓存数组return fib(n);}private static BigInteger fib(int n) {if (n <= 1) {return BigInteger.valueOf(n);}// 如果缓存中已经有了斐波那契数列的第n项的值，则直接返回缓存结果if (memoization[n] != null) {return memoization[n];}// 如果缓存中没有斐波那契数列的第n项的值，则进行递归计算，并将结果存入缓存数组中memoization[n] = fib(n - 1).add(fib(n - 2));return memoization[n];}public static void main(String[] args) {int n1 = 10000;long startTime1 = System.currentTimeMillis();BigInteger result1 = fibonacciWithMemoization(n1);long endTime1 = System.currentTimeMillis();long elapsedTime1 = endTime1 - startTime1;System.out.println("Fibonacci(" + n1 + ") = " + result1);System.out.println("程序运行时间：" + elapsedTime1 + " 毫秒");int n2 = 15000;long startTime2 = System.currentTimeMillis();BigInteger result2 = fibonacciWithMemoization(n2);long endTime2 = System.currentTimeMillis();long elapsedTime2 = endTime2 - startTime2;System.out.println("Fibonacci(" + n2 + ") = " + result2);System.out.println("程序运行时间：" + elapsedTime2 + " 毫秒");int n3 = 18000;long startTime3 = System.currentTimeMillis();BigInteger result3 = fibonacciWithMemoization(n3);long endTime3 = System.currentTimeMillis();long elapsedTime3 = endTime3 - startTime3;System.out.println("Fibonacci(" + n3 + ") = " + result3);System.out.println("程序运行时间：" + elapsedTime3 + " 毫秒");}
}

（三）性能分析

  1. 时间复杂度：计算斐波那契数列的第n项需要计算前面的n-1项和n-2项，每一项的计算都需要常数时间，因此时间复杂度为O(n)。在递归方法中，对于每个n，我们最多只需计算一次，然后将结果存入缓存数组中，之后再次需要计算时直接从缓存中取值，不再进行重复计算。因此，整个递归过程的时间复杂度为O(n)。

  2. 空间复杂度：在递归方法中使用了一个长度为n+1的数组来存储斐波那契数列的值，因此空间复杂度为O(n+1)，即O(n)。此外，递归调用时的函数调用栈也会占用一定的空间，其空间复杂度取决于递归的最大深度。在这种情况下，最大深度为n，因此额外的空间复杂度也为O(n)。综合起来，整个算法的空间复杂度为O(n)。

实际运行发现当n为10000耗7毫秒，n为15000时耗时4毫秒，性能变好了，但当n为18000的时候耗时7毫秒性能上又变差了，然后n为18100时出现StackOverflowError。性能比采用递归+HashMap缓存方式还差一些。原因还是递归的调用栈是有限的，性能上破不了18100。

五、数组缓存+顺序迭代

（一）解法思路

数组缓存+顺序迭代，结合了动态规划的思想和迭代的方式来计算斐波那契数列。

  • 首先初始化一个数组，用来存储斐波那契数列的值。数组的长度至少为n+1，以存储从0到n的所有斐波那契数列的值。将斐波那契数列的前两项初始化为0和1，并将其存入数组中。
  • 从第三项开始，通过迭代的方式依次计算斐波那契数列的每一项的值。对于第i项，可以通过前两项的值相加得到，然后将计算得到的值存入数组中。
  • 在计算完成后，数组中的最后一项即为所求的斐波那契数列的第n项的值，将其作为结果返回即可。

其核心是利用数组来存储已经计算过的斐波那契数列的值，并通过顺序迭代的方式逐步计算下一项的值，由于是顺序迭代计算，不需要额外的函数调用栈空间，因此效率更高。

（二）代码展示

package org.zyf.javabasic.algorithm;import java.math.BigInteger;/*** @program: zyfboot-javabasic* @description: 使用数组缓存+顺序迭代方法来计算斐波那契数列* @author: zhangyanfeng* @create: 2024-04-24 23:42**/
public class IterativeArrayFibonacci {public static BigInteger fibonacci(int n) {if (n <= 1) {return BigInteger.valueOf(n);}// 初始化数组缓存BigInteger[] fib = new BigInteger[n + 1];fib[0] = BigInteger.ZERO;fib[1] = BigInteger.ONE;for (int i = 2; i <= n; i++) {// 顺序迭代计算每一项的值fib[i] = fib[i - 1].add(fib[i - 2]);}// 返回斐波那契数列的第n项的值return fib[n];}public static void main(String[] args) {int[] nValues = {10000, 15000, 20000,30000,40000,10000000};for (int n : nValues) {long startTime = System.currentTimeMillis();BigInteger result = fibonacci(n);long endTime = System.currentTimeMillis();long elapsedTime = endTime - startTime;System.out.println("Fibonacci(" + n + ") = " + result);System.out.println("程序运行时间：" + elapsedTime + " 毫秒");}}
}

（三）性能分析

  1. 时间复杂度：计算斐波那契数列的第n项时，需要顺序计算从第2项到第n项的所有值。在每次计算时，只需对前两项进行一次加法操作，因此每次计算的时间复杂度为O(1)。因此，总体的时间复杂度为O(n)。

  2. 空间复杂度：为了存储计算过的斐波那契数列的值，我们需要一个长度为n+1的数组。因此，空间复杂度为O(n+1)，即O(n)。

实际运行发现当n为10000-20000耗时5毫秒，n为30000时耗时17毫秒，性能变好了，但当n为40000的时候耗时29毫秒性能上又变差了，然后n为11000万时出现OutOfMemoryError。

这是因为在计算斐波那契数列的过程中，需要创建一个长度为n+1的数组来存储计算过的斐波那契数值，而11000万这样的大数会导致需要分配非常大的内存空间来存储数组，超出了Java虚拟机默认的堆内存大小。

要解决这个问题，可以通过增加Java虚拟机的堆内存大小来提供更多的内存空间，可以通过设置-Xmx参数来实现。例如，可以使用命令java -Xmx4g zyfboot来将堆内存大小设置为4GB。然而，对于非常大的n值，即使增加堆内存大小也可能会遇到内存不足的问题。

六、取消缓存直接采用迭代优化

（一）解法思路

取消缓存，采用迭代的方式来计算斐波那契数列是一种简单而有效的方法，通过循环迭代计算斐波那契数列的每一项，不需要额外的存储空间来缓存已经计算过的值，从而节省了内存空间，同时也提高了效率。

  • 首先，我们将斐波那契数列的前两项初始化为0和1，作为初始状态。
  • 然后，通过一个循环来迭代计算斐波那契数列的每一项。从第三项开始，每一项都是前两项的和。
  • 在计算每一项时，需要更新前两项的值，使其保持最新的状态，以便下一次迭代使用。
  • 重复以上步骤，直到计算到第n项为止。计算完成后，第n项的值即为所求的斐波那契数列的值。

采用迭代的方式计算斐波那契数列不需要额外的存储空间，只需要少量的变量来保存前两项的值以及当前项的值。因此，它的空间复杂度为O(1)，效率很高。

（二）代码展示

package org.zyf.javabasic.algorithm;import java.math.BigInteger;/*** @program: zyfboot-javabasic* @description: 采用迭代方式计算斐波那契数列* @author: zhangyanfeng* @create: 2024-04-24 23:58**/
public class IterativeFibonacci {public static BigInteger fibonacci(int n) {if (n <= 1) {return BigInteger.valueOf(n);}BigInteger a = BigInteger.ZERO;BigInteger b = BigInteger.ONE;BigInteger temp;for (int i = 2; i <= n; i++) {temp = b;b = a.add(b);a = temp;}return b;}public static void main(String[] args) {int[] nValues = {10000, 20000, 80000,800000,1000000,5000000,10000000,90000000};for (int n : nValues) {long startTime = System.currentTimeMillis();BigInteger result = fibonacci(n);long endTime = System.currentTimeMillis();long elapsedTime = endTime - startTime;System.out.println("Fibonacci(" + n + ") = " );System.out.println("程序运行时间：" + elapsedTime + " 毫秒");}}
}

（三）性能分析

  1. 时间复杂度：在迭代过程中，每次循环都只需要进行一次加法操作，因此每次循环的时间复杂度为O(1)。总共需要进行n-1次循环（从第3项开始到第n项），因此总体的时间复杂度为O(n)。

  2. 空间复杂度：采用迭代方式计算斐波那契数列不需要额外的存储空间来存储计算过的值，只需要少量的变量来保存前两项的值以及当前项的值。因此，空间复杂度为O(1)，即常数级别的空间复杂度。

实际运行发现当n为10000耗5毫秒，n为20000时耗时5毫秒，当n为80000的时候耗时64毫秒，当n为80万的时候耗时4781毫秒，当n为100万的时候耗时4782毫秒，当n为500万的时候耗时182683毫秒（182.683秒），当n为1000万的时候耗时721534毫秒（721.534秒）.......。当数量级很大时，其性能也就极具恶化了。

七、用初等代数推导公式解法

（一）解法分析

利用初等代数推导斐波那契数列的公式解法是一种高效的方法，可以在O(1)的时间复杂度内得到斐波那契数列的第n项的值。这种方法利用了斐波那契数列的性质和数学推导，而不需要进行递归或迭代的计算。

斐波那契数列的公式解法基于以下两个定理：

  1. 通项公式：斐波那契数列的第n项可以通过以下通项公式来计算：

    其中，

    其为黄金分割比。

  2. 斐波那契数列的性质：当n为正整数时，。

利用以上两个定理，可以得到斐波那契数列的公式解法：

  1. 首先，计算𝜙和−𝜙的幂次方，可以通过快速幂算法来实现。

  2. 然后，利用通项公式计算斐波那契数列的第n项的值。

（二）代码展示

package org.zyf.javabasic.algorithm;import java.math.BigDecimal;/*** @program: zyfboot-javabasic* @description: 使用初等代数推导的公式解法* @author: zhangyanfeng* @create: 2024-04-25 00:26**/
public class FormulaFibonacciPerformance {public static long getFibonacciByFormula(int index) {double temp = Math.sqrt(5.0);return (long) ((Math.pow((1 + temp) / 2, index) - Math.pow((1 - temp) / 2, index)) / temp);}public static void main(String[] args) {int[] nValues = {100000, 2100000000};for (int n : nValues) {long startTime = System.nanoTime();long result = getFibonacciByFormula(n);long endTime = System.nanoTime();long elapsedTime = endTime - startTime;System.out.println("Fibonacci(" + n + ") = " + result);System.out.println("程序运行时间：" + elapsedTime + " 纳秒");}}
}

（三）性能分析

  1. 时间复杂度：计算黄金分割比的幂次方和斐波那契数列的第n项都可以在常数时间内完成，因此整体的时间复杂度为O(1)。

  2. 空间复杂度：该方法不需要额外的存储空间来保存斐波那契数列的中间结果，因此空间复杂度为O(1)，即常数级别的空间复杂度。

实际运行发现当n为10万时耗时1600纳秒，n为21亿时耗时1084纳秒（0.001084 毫秒）。

但初等代数推导的公式解法在处理较大的n值时会遇到一些问题：

  1. 黄金分割比（𝜙）是一个无理数，其幂次方的计算会导致精度丢失问题。计算机的浮点数表示有限，超过一定的位数后会出现精度丢失，导致计算结果不准确。

  2. 由于精度丢失和计算效率问题，当n超过一定大小（如n>71）时，计算结果会变得不可靠，与真实的斐波那契数列的值存在较大偏差。

  3. 尽管空间复杂度为O(1)，但计算黄金分割比的幂次方和斐波那契数列的第n项所涉及的数值非常大，可能需要大量的内存空间来存储这些数值，导致内存消耗增加。

虽然初等代数推导的公式解法具有常数级别的时间复杂度和空间复杂度，但在处理较大的n值时会遇到精度丢失、计算效率低下、结果不可靠等问题，因此不适用于处理超过一定大小的n值。

八、矩阵解法

（一）解法分析

利用矩阵的特性和矩阵乘法的性质，将斐波那契数列的计算问题转化为矩阵乘法的问题，从而避免了传统递归或迭代算法中的重复计算，提高了计算效率。该方法的基本思想是将斐波那契数列的递推关系表示为矩阵形式，然后通过矩阵的幂运算来快速计算出第n项的值。

具体而言，矩阵解法首先定义一个2x2的矩阵F，称为斐波那契矩阵，其元素为

然后，利用矩阵的幂运算，通过快速幂算法来计算斐波那契数列的值。在计算过程中，需要注意选择合适的数据类型以避免数值溢出的问题。

实现步骤：

  • 首先，对输入的n值进行有效性检查，确保其为正整数。
  • 初始化斐波那契矩阵如上图，记为initMatrix。
  • 迭代计算矩阵initMatrix的n-2次幂（因为斐波那契数列从第3项开始才适用矩阵解法），得到结果矩阵tem。
  • 最终结果存储在tem矩阵的第一行第一列位置，即tem[0][0]，返回该值作为第n项的斐波那契数。

（二）代码展示

package org.zyf.javabasic.algorithm;/*** @program: zyfboot-javabasic* @description: 使用矩阵解法计算斐波那契数列* @author: zhangyanfeng* @create: 2024-04-25 00:54**/
public class MatrixFibonacci {public static long getFibonacciByMatrix(int index) {// 检查输入的索引是否合法if (index <= 0) {throw new IllegalArgumentException("Index must be a positive integer");}// 初始斐波那契矩阵long[][] fibonacciMatrix = {{1, 1}, {1, 0}};// 迭代计算矩阵的 index - 2 次幂for (int i = 2; i < index; i++) {fibonacciMatrix = matrixMultiply(fibonacciMatrix, new long[][]{{1, 1}, {1, 0}});}// 结果存储在矩阵的第一行第一列位置return fibonacciMatrix[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.currentTimeMillis();long fibonacci100000 = MatrixFibonacci.getFibonacciByMatrix(100000);long endTime1 = System.currentTimeMillis();long elapsedTime1 = endTime1 - startTime1;System.out.println("Fibonacci(100000) = " + fibonacci100000);System.out.println("耗时：" + elapsedTime1 + "毫秒");// 计算第2100000000项的斐波那契数long startTime2 = System.currentTimeMillis();long fibonacci2100000000 = MatrixFibonacci.getFibonacciByMatrix(2100000000);long endTime2 = System.currentTimeMillis();long elapsedTime2 = endTime2 - startTime2;System.out.println("Fibonacci(2100000000) = " + fibonacci2100000000);System.out.println("耗时：" + elapsedTime2 + "毫秒");}
}

（三）性能分析

  1. 时间复杂度：因为矩阵解法使用快速幂算法来计算斐波那契数列的第n项，每次迭代都会将指数除以2，因此迭代次数为log₂n。

  2. 空间复杂度：矩阵解法不需要保存额外的中间结果，只需要使用一个固定大小的矩阵来进行计算，因此空间复杂度是常数级别的。

实际运行发现当n为10万时耗时19毫秒，n为21亿时耗时14947毫秒。

矩阵解法的优点在于其时间复杂度为O(log n)，相较于传统的递归或迭代算法更为高效。此外，由于不需要保存中间结果，节省了内存空间。然而，需要注意的是，在计算过程中可能会出现数据溢出或精度问题，特别是对于非常大的n值。因此，在实际应用中，需要谨慎选择数据类型和算法，并根据具体情况进行优化。

九、矩阵解法+快速幂

（一）解法分析

基本思想是利用矩阵乘法的性质，将斐波那契数列的递推关系表示为矩阵形式，然后通过快速幂算法来快速计算矩阵的高次幂，从而得到斐波那契数列的第n项的值。

具体而言，该方法首先定义一个2x2的斐波那契矩阵F，其元素为

然后利用快速幂算法来计算矩阵F的高次幂，即F^{n}。通过将指数n转化为二进制形式，并利用矩阵的乘法性质，可以在O(log n)的时间复杂度内计算出F^{n}。最后，将得到的矩阵𝐹𝑛Fn与初始矩阵(10)(10​)相乘，得到的结果的第一个元素即为斐波那契数列的第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 + "毫秒");}
}

（三）性能分析

  1. 时间复杂度分析：计算第n项斐波那契数需要进行快速幂运算，时间复杂度为O(log n)。这是因为快速幂算法的时间复杂度为O(log n)，在算法中只需进行log n次乘法运算。在快速幂运算中，每次矩阵相乘的时间复杂度为O(1)。因此，总的时间复杂度为O(log n)。
  2. 空间复杂度分析：算法中使用的空间主要由两个矩阵所占用的空间决定。这两个矩阵分别是初始矩阵和结果矩阵，都是固定大小的2x2矩阵。因此，空间复杂度为O(1)，即常数级别的空间复杂度。

实际运行发现当n为10万时耗时0.013125毫秒，n为21亿时耗时0.022042毫秒。

矩阵解法结合快速幂的斐波那契数列算法具有优秀的时间复杂度O(log n)和空间复杂度O(1)，适用于需要高效计算大数值斐波那契数列的场景。

十、最优解分析

在实际应用中，结合快速幂的矩阵解法确实是计算斐波那契数列的最优解之一，尤其是对于大数值的情况。然而，并不是所有情况下都适合使用这种方法。

  • 对于小规模的斐波那契数列计算（比如前几十项），简单的递归或迭代方法可能更为简单和高效。
  • 对于需要计算大数值斐波那契数列的情况，结合快速幂的矩阵解法通常是最优的选择之一，因为它具有较低的时间复杂度和空间复杂度。

然而，在某些特定情况下，可能存在其他更为优化的解法。例如，针对特定斐波那契数列的性质和规律，可能会有更快速的算法或更有效的数学公式可以利用。因此，虽然矩阵解法结合快速幂是一种非常有效的方法，但并不排除其他可能存在的最优解法。


http://www.mrgr.cn/p/60025723

相关文章

UE5 GAS开发P34 游戏效果理论

UE5 GAS开发P34 游戏效果理论

GameplayEffects Attributes&#xff08;属性&#xff09;和Gameplay Tags&#xff08;游戏标签&#xff09;分别代表游戏中实体的特性和标识。 Attributes&#xff08;属性&#xff09;&#xff1a;Attributes是用来表示游戏中实体的特性或属性的值&#xff0c;例如生命值、…
阅读更多...
docker - [10] 容器数据卷

docker - [10] 容器数据卷

1、什么是容器数据卷？2、容器数据卷的使用将应用和环境打包成一个镜像，然后发布启动就成为一个容器了。 一、什么是容器数据卷容器数据卷（Container Data Volumes）是Docker管理的一种特殊类型的存储区域，它为容器提供了一种持久化数据、共享数据以及与宿主机或其他容器之…
阅读更多...
dial tcp 192.168.0.190:443: connect: connection refused

dial tcp 192.168.0.190:443: connect: connection refused

1、场景 用nerdctl登录镜像仓库192.168.0.190&#xff08;Harbor&#xff09;&#xff0c;报错 ERRO[0006] failed to call tryLoginWithRegHost error"failed to call rh.Client.Do: Get \"https://192.168.0.190/v2/\": dial tcp 192.168.0.190:…
阅读更多...
shell脚本文本处理工具

shell脚本文本处理工具

声明： 以下内容为个人笔记，内容不完全正确，请谨慎参考。 文本处理工具 cut: cut 工作是“剪”，具体来说就是在文件中负责剪切数据。cut 命令从文件的每个行剪切字节、字符和字段输出。 1、基本语法： cut [选项参数] filename 说明：默认分隔符是副表符 2、选项参数说明 选…
阅读更多...
网络隔离的最小配置

网络隔离的最小配置

作者：任云康，青云科技研发工程师前言 对于项目下的网络隔离，有用户提出了以下疑问：网络隔离是针对 Pod 的吗？ 网络隔离的最小配置是什么？配置后，哪些是可以访问的，哪些是不可以访问的？ 通过 Ingress 暴露、LB 类型的 Service 暴露、NodePort 类型的 Service 暴露的流量…
阅读更多...
输入‘（’和‘）’判断字符串有效的函数算法

输入‘（’和‘）’判断字符串有效的函数算法

`// 设置一个函数，通过输入键盘中的‘（’和‘）’判断字符串是否有效 // 顺序表中的元素数据类型是char类型 typedef char DataType_t; // 创建顺序栈SequenceStack各项数据（栈底地址 栈容量 栈顶元素下标）的结构体 typedef struct SequenceStack { DataType_t *Bottom;…
阅读更多...
ctfshow web41-web50

ctfshow web41-web50

web41 代码审计 <?php if(isset($_POST[c])){$c $_POST[c]; if(!preg_match(/[0-9]|[a-z]|\^|\|\~|\$|\[|\]|\{|\}|\&|\-/i, $c)){eval("echo($c);");} }else{highlight_file(__FILE__); } ?> 过滤了&#xff1a;[0-9] [a-z] ^ ~ $ [ ] { } & -…
阅读更多...
Suno：一键生成原创音乐的AI！还不赶紧体验一下？

Suno：一键生成原创音乐的AI！还不赶紧体验一下？

最近一两年，AI的发展是飞速的，从AI聊天到AI绘画，再到AI视频，一次一次的刷新我们的认知，最近AI一键生成音乐也出来了。不知道大家有没有刷到过。今天盘哥就来把它分享给大家，你也可以一键生成专属于自己的音乐。01 - Suno（网站） 它就是一个可以一键生成音乐的AI网站，我…
阅读更多...
详解Al作画算法原理

详解Al作画算法原理

ChatGPT AI作画算法&#xff0c;又称为AI图像生成算法&#xff0c;是一种人工智能技术&#xff0c;它可以根据给定的输入自动生成图像。这类算法近年来变得非常流行&#xff0c;尤其是随着深度学习技术的发展。这里我将聚焦于目前最先进的一类AI作画算法&#xff0c;即生成对抗…
阅读更多...
3种方式自动化控制APP

3种方式自动化控制APP

自动化控制APP不管是在工作还是生活方面，都可以帮助我们高效地完成任务，节省时间和精力。本文主要介绍自动化控制APP的3种常用方式。 1、Python + adb这种方式需要对Android有一些基本的了解。adb是一种用于调试Android应用程序的工具。使用Python和adb可以轻松实现自动化控制…
阅读更多...
Appium控件交互策略：优化自动化测试效率的关键方法

Appium控件交互策略：优化自动化测试效率的关键方法

简介 与 Web 元素操作一样（参考 Selenium Web 元素操作），定位到 APP 控件元素后，可以对控件进行一系列的操作，实现与 APP 交互，比如点击、文本输入、元素属性获取等。 控件交互常用方法 常见操作点击方法 element.click()。 输入操作 element.send_keys(appium)。 清除操…
阅读更多...
STM32玩转物联网实战篇：5.ESP8266 WIFI模块MQTT通信示例详解

STM32玩转物联网实战篇：5.ESP8266 WIFI模块MQTT通信示例详解

1、准备开发板 开发板功能区分布图 开发板俯视图 2、实验讲解 在之前的章节中&#xff0c;已经讲解过了MQTT的通讯原理和组包过程&#xff0c;现在开始手把手的教大家用代码来实现连接MQTT平台以及数据的交互&#xff0c;实际上这篇文章已经拖更接近两年了&#xff0c;非常…
阅读更多...
Part-DB 配置流程

Part-DB 配置流程

介绍 Part-DB是一个开源的器件管理工具，博主用于管理个人的电子器材，最近捣鼓了一下这个工具，由于手头还有一块闲置的赛昉星光2的开发板，所以我打算一起拿来捣鼓一下，如果不成功，就用树莓派（生气😠） 1.安装 大家可以直接按照 官方安装指导 来安装即可，我也是参考官方…
阅读更多...
【已解决简单好用】notepad++怎么设置中文

【已解决简单好用】notepad++怎么设置中文

打开Notepad软件。点击软件界面顶部菜单栏中的“Settings”选项。在下拉菜单中选择“Preferences”进行语言设置。在打开的设置窗口中&#xff0c;找到“General”选项。在“General”选项中&#xff0c;找到“Localization”&#xff08;界面语言&#xff09;项。在下拉菜单中…
阅读更多...
『 论文解读 』大语言模型（LLM）代理能够自主地利用1 day漏洞，利用成功率竟高达87%，单次利用成本仅8.8美元

『 论文解读 』大语言模型（LLM）代理能够自主地利用1 day漏洞，利用成功率竟高达87%，单次利用成本仅8.8美元

1. 概览 该论文主要展示了大语言模型LLM代理能够自主利用现实世界的 1 day 漏洞。研究我发现&#xff0c; GPT-4 在提供了CVE描述的情况下&#xff0c;能够成功利用 87% 的漏洞。 这与其他测试模型&#xff08;如 GPT-3.5 和其他开源 LLM &#xff09;以及开源漏洞扫描器&…
阅读更多...
面试：ThreadLocal

面试：ThreadLocal

目录 1、ThreadLocal可以实现〔资源对象】的线程隔离&#xff0c;让每个线程各用各的【资源对象】&#xff0c;避免争用引发的线程安全问题 2、ThreadLocal同时实现了线程内的资源共享 3、原理 4、为什么ThreadLocalMap 中的 key (即 ThreadLocal &#xff09;要设计为弱引用…
阅读更多...
双向循环链表

双向循环链表

双向循环链表的原理及相应功能的代码实现。双向循环链表 原理与应用 双向循环链表与双向链表的区别：指的是双向循环链表的首结点中的prev指针成员指向链表的尾结点，并且双向循环链表的尾结点里的next指针成员指向链表的首结点，所以双向循环链表也属于环形结构。双向循环链表…
阅读更多...
选择企业文件同步备份系统 需要注意这几点

选择企业文件同步备份系统 需要注意这几点

企业文件同步备份系统，是几乎每个企业都会用到的，都是为了保障业务数据的连续性、提高数据的可用性，让数据价值最大化。 企业在进行文件同步备份时可能会面临的问题包括： 1、数据传输效率低下：在面对海量小文件时，传统备份方式需要对每个文件进行打开、读取、关闭操作，…
阅读更多...
基于python+django+mysql农业生产可视化系统

基于python+django+mysql农业生产可视化系统

博主介绍&#xff1a; 大家好&#xff0c;本人精通Java、Python、C#、C、C编程语言&#xff0c;同时也熟练掌握微信小程序、Php和Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我有丰富的成品Java、Python、C#毕设项目经验&#xff0c;能够为学生提供各类…
阅读更多...
Django中间件的源码解析流程（上）——中间件载入的前置

Django中间件的源码解析流程（上）——中间件载入的前置

目录 1. ​前言​ 2. 请求的入口 3. 中间件加载的入口 4. 源码中的闭包实现 5. 最后 1. 前言 哈喽&#xff0c;大家好&#xff0c;我是小K,今天咋们分享的内容是&#xff1a;在学会Django中间件之后&#xff0c; 我们继续深入底层源码。 在执行中间件时请求到来总是从前往后…
阅读更多...
推荐文章

Copyright @ 2022~2023