😀前言
斐波那契数列作为经典的数学问题，在计算机领域有着广泛的应用和研究价值。本文将探讨如何高效地求解斐波那契数列的第 n 项，通过不同的算法实现，并分析它们的时间复杂度和空间复杂度。

🏠个人主页：尘觉主页

斐波那契数列

题目链接

斐波那契数列是一个满足的数列

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
数据范围：1≤n≤40
要求：空间复杂度 O(1)，时间复杂度 O(n) ，本题也有时间复杂度 O(logn) 的解法

牛客网

题目描述

求斐波那契数列的第 n 项，n <= 39。

解题思路

如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。

递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。

public int Fibonacci(int n) {if (n <= 1)return n;int[] fib = new int[n + 1];fib[1] = 1;for (int i = 2; i <= n; i++)fib[i] = fib[i - 1] + fib[i - 2];return fib[n];
}

考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。

public int Fibonacci(int n) {if (n <= 1)return n;int pre2 = 0, pre1 = 1;int fib = 0;for (int i = 2; i <= n; i++) {fib = pre2 + pre1;pre2 = pre1;pre1 = fib;}return fib;
}

由于待求解的 n 小于 40，因此可以将前 40 项的结果先进行计算，之后就能以 O(1) 时间复杂度得到第 n 项的值。

public class Solution {private int[] fib = new int[40];public Solution() {fib[1] = 1;for (int i = 2; i < fib.length; i++)fib[i] = fib[i - 1] + fib[i - 2];}public int Fibonacci(int n) {return fib[n];}
}

😄总结

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞