问题描述:
斐波那契数, 通常用 F(n) 表示, 形成的序列称为斐波那契数列. 该数列由 0 和 1 开始, 后面的每一项数字都是前面两项数字的和. 也就是:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N> 1.
给定 N, 计算 F(N).
示例 :
输入: 2
输出: 1
解释: F(2) = F(1) + F(0) = 1 + 0 = 1.
问题分析:
由于计算任何一个第 n(n>= 2) 项的数都需要知道其前面两个数, 即需要知道 n-1 和 n-2 是多少, 然后两个相加得到结果, 但是问题来了, 要知道 n-1, 就要需要知道 n-2, 要知道 n-2 就需要知道 n-3, 会一直这样的循环递归下去, 一直到第一个数, 第二个, 第三个....... 再反推回来. 那就很明显了, 大家第一时间想到的方法便是递归, 就下来实现一下:
方法一: 递归实现
- public class Solution {
- public int fib(int n) {
- if(n <= 1){
- return n;
- }
- return fib(n-1) + fib(n-2);
- }
- }
问题分析:
先看一下递归图:
由于很多数的计算都要重复很多次, 效率并不高, 时间复杂度达到了 O(2^n), 是斐波那契数计算中 时间复杂度最大, 最不可取的方法.
空间复杂度: O(n), 堆栈中需要的空间与 N 成正比, 堆栈会跟踪 fib(n) 的调用, 随着堆栈的不断增长 如果没有足够的内存则会出现 StackOverflowError 异常.
注: 定义为 int 型时, 最大只能求到 n = 46,f(46) = 1836311903, 而 f(47) = -1323752223, 因为超出了 int 型数值的最大范围.
算法改进:
使用递归的同时, 使用记忆化方式存储已经计算过的数据, 减少不必要的重复计算, 可以使时间复杂度降到 O(N), 同时空间复杂度也是 O(N). 具体的实现是使用一个数组, 把每次计算过的值都存储进去, 当再次使用这个数的时候, 直接返回, 不需要再进行递归.
方法二: 记忆化自底向上递归
- public class Solution {
- public int fib(int n) {
- if(n <= 1){
- return n;
- }
- int[] memo = new int[n+1];
- memo[1] = 1;
- for(int i = 2;i <= n; i++){
- // 自底向上填充数组, 一直到需要的那个数
- memo[i] = memo[i-1] + memo[i-2];
- }
- return memo[n];
- }
- }
最后:
限于水平有限, 斐波那契数的实现还有很多种方法, 不能一一列举, 当其中大部分都有类似的思想.
水文中如有不准确或是错误之处, 还望指出. 谢谢~~~
来源: https://www.cnblogs.com/coding-996/p/12309481.html