黑马程序员技术交流社区

标题: 【广州前端】- 斐波那契数列-从递归到动态规划 [打印本页]

作者: 社会佩奇 时间: 2019-9-18 10:33
标题: 【广州前端】- 斐波那契数列-从递归到动态规划
本帖最后由社会佩奇于 2019-9-18 10:52 编辑

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

如果设F(n）为该数列的第 n 项（n∈N*）
那么这句话可以写成如下形式：F(n)=F(n-1)+F(n-2)

设计一个函数，调用该函数传入 n，可以计算斐波那契数列第n项的数字

原始递归版

[JavaScript] 纯文本查看 复制代码

function fib(n) {

  if (n == 1 || n == 2) return 1

  return fib(n - 1) + fib(n - 2)

}

例 n=20 时，红色圈出的 fib(18)被计算了 2 次，以 fib(18)为根的递归树体量巨大，消耗巨量时间。
且不止一个类似 fib(18)被重复计算。
原始递归版效率极低。

可以通过下图看出，红色是调用 fib 函数传入的 n 值

当 n 值为 46 时，需要的总时间已经突破10s

当 n 值为 47 时，需要的总时间已经需要29s！

计算时间呈指数级爆炸！

时间复杂度为 O(2^n)

字典递归版

[JavaScript] 纯文本查看 复制代码

var fibHelper = {}

function fib(n) {

  if (n == 1 || n == 2) return 1

  if (fibHelper[n]) return fibHelper[n]

  fibHelper[n] = fib(n - 1) + fib(n - 2)

  return fibHelper[n]

}

递归树

递归树剪枝：把已经计算过的 n 值存到字典中，需要用时直接查字典
所有的 n 值计算 1 次就行了，极大减少了子节点重复计算的问题
计算方向是自顶向下的

直接计算 n = 47，需要的总时间仅需6.29ms，同原始递归版比较不是一个数量级

时间复杂度是 O(n)

动态规划版

[JavaScript] 纯文本查看 复制代码

function fib(n) {

  var arr = [0]

  arr[1] = arr[2] = 1

  for (let i = 3; i <= n; i++) {

    arr = arr[i - 1] + arr[i - 2]

  }

  return arr[n]

}

图解

通项公式：f(n) = f(n-1) + f(n-2)
f(n) 看做时状态 n，这个状态 n 是状态 n-1 和状态 n-2 相加转移而来，就是状态转移

同样计算n = 47，动态规划版和字典递归版在耗时上几乎没有差别

动态规划优化版

当前状态只和之前的两个状态有关，其实并不需要数组 arr 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化：

优化后,空间复杂度降为 O(1)

[JavaScript] 纯文本查看 复制代码

function fib(n) {

  if (n < 2) return n

  let [prev, curr] = [1, 1]

  for (let i = 1; i < n - 1; i++) {

    let sum = prev + curr;

    [prev, curr] = [curr, sum]

  }

  return curr

}

1568451514763.png (8.9 KB, 下载次数: 5)

1568452088387.png (7.19 KB, 下载次数: 8)

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2