乐趣区

关于算法:算法-详解斐波那契数列问题

jiezi

本篇是学习了《趣学算法（第 2 版）》第一章之后总结的。

上一篇讲到了等比数列求和问题，求 $S_n = 1 + 2 + 2^2 + 2^3 + … + 2^{63}=？$，该函数属于 爆炸增量函数，如果采纳惯例运算，则要思考算法的工夫复杂度。

算法知识点

  • 斐波那契数
  • 动静布局（拆分子问题；记住过往，缩小反复计算）

算法题目

假如第 1 个月有 1 对初生的兔子，第 2 个月进入成熟期，第 3 个月开始生养兔子，而 1 对成熟的兔子每月会生
1 对兔子，兔子永不死去..…那么，由 1 对初生的兔子开始，12 个月后会有多少对兔子呢？

做题思路

这个数列有如下非常显著的特点：从第 3 个月开始，$ 当月的兔子数 = 上月兔子数 + 当月新生兔子数 $，而 $ 当月新生兔子数 = 上上月的兔子数 $。因而，后面相邻两项之和便形成后一项，换言之：
$$ 当月的兔子数 = 上月兔子数 + 上上月的兔子数 $$

斐波那契数如下：

1，1，2，3，5，8，13，21，34 ......

递归表达式

$$F(n)=
\begin{cases}
1&，\text{n=1}\
1&，\text{n=2}\
F(n-1) + F(n-2)&，\text{n>2}
\end{cases}$$

依据递归表达式，初步的算法代码如下：

const fbn = (n) => {if (n == 1 || n == 2) {return 1} else {return fbn(n-2) + fbn(n-1)
    }
}

让咱们看一下下面算法的工夫复杂度，也就是计算的总次数 $T(n)$

工夫复杂度

工夫复杂度算的是最坏状况下的工夫复杂度

n= 1 时，T(n)=1
n= 2 时，T(n)=1；n= 3 时，T(n)=3; // 调用 Fib1(2)和 Fib1(1)并执行一次加法运算(Fib1(2)+Fib1(1))

当 n >2 时须要别离调用 fbn(n-1) 和fbn(n-2)，并执行一次加法运算，换言之：
$$n\gt2 时，T(n)=T(n-1)+T(n-2)+1;$$

所以，$T(n) >= F(n)$

问题来了，怎么判断 T(n) 属于算法工夫复杂度的哪种类型呢？

办法一：

画出递归树，每个节点示意计算一次

一棵 满二叉树 ， 节点总数就和树的高度呈指数关系

递归树 F(n)外面存在满二叉树，所以 工夫复杂度是指数阶的。

办法二：

应用公式进行递推

因为工夫复杂度算的是最坏状况下的工夫复杂度，所以计算第一个括号内的即可

即：$T(n) = O(2^n)$，工夫复杂度是 指数阶 的

算法改良

升高工夫复杂度

不难发现：下面基于递归表达式的算法，存在大量的反复计算，增大了算法的工夫复杂度，所以咱们能够做出如下改良，以缩小工夫复杂度

// 利用数组记录过往的值，间接应用，防止反复计算
const fbn2 = (n) => {let arr = new Array(n + 1); // 定义 n + 1 长度的数组
  arr[1] = 1;
  arr[2] = 1;
  for (let i = 3; i <= n; i++) {arr[i] = arr[i - 1] + arr[i - 2]
  }
  return arr[n]
}

很显然下面算法的工夫复杂度是 $O(n)$，工夫复杂度从指数阶降到了多项式阶。

因为下面算法应用数组记录了所有项的值，所以，算法的空间复杂度变成了 $O(n)$，咱们能够持续改良算法，来升高算法的空间复杂度

升高空间复杂度

采纳长期变量，来迭代记录上一步计算出来的值，代码如下：

const fbn3 = (n) => {if (n === 1 || n === 2) {return 1;}
  let pre1 = 1 // pre1，pre2 记录后面两项
  let pre2 = 1
  let tmp = ''

  for (let i = 3; i <= n; i++) {
    tmp = pre1 + pre2 // 2
    pre1 = pre2 // 1
    pre2 = tmp // 2
  }
  return pre2
}

应用了三个辅助变量，工夫复杂度还是 $O(n)$，空间复杂度降为 $O(1)$

测试算法计算工夫

// 斐波那契数列
// 1，1，2，3，5，8，13，21，34 ......

const fbn = (n) => {if (n == 1 || n == 2) {return 1} else {return fbn(n-2) + fbn(n-1)
    }
}
console.time('fbn')
console.log('fbn(40)=', fbn(40))
console.timeEnd('fbn')

// 利用数组记录过往的值，间接应用，防止反复计算
const fbn2 = (n) => {let arr = new Array(n + 1); // 定义 n + 1 长度的数组
  arr[1] = 1;
  arr[2] = 1;
  for (let i = 3; i <= n; i++) {arr[i] = arr[i - 1] + arr[i - 2]
  }
  return arr[n]
}

console.time('fbn2')
console.log('fbn2(40)=', fbn2(40))
console.timeEnd('fbn2')

const fbn3 = (n) => {if (n === 1 || n === 2) {return 1;}
  let pre1 = 1 // pre1，pre2 记录后面两项
  let pre2 = 1
  let tmp = ''

  for (let i = 3; i <= n; i++) {
    tmp = pre1 + pre2 // 2
    pre1 = pre2 // 1
    pre2 = tmp // 2
  }
  return pre2
}

console.time('fbn3')
console.log('fbn3(40)=', fbn3(40))
console.timeEnd('fbn3')

测试后果如下：

fbn(40)= 102334155
fbn: 667.76ms
fbn2(40)= 102334155
fbn2: 0.105ms
fbn3(40)= 102334155
fbn3: 0.072ms

小结

能不能持续降阶，使算法的工夫复杂度更低呢？
本质上，斐波那契数列的工夫复杂度还能够降到对数阶 $O(logn)$，好厉害!!! 前面持续摸索吧

算法作为一门学识，有两条简直平行的线索：

  1. 数据结构（数据对象）：数、矩阵、汇合、串、排列、图、表达式、散布等。
  2. 算法策略：贪婪策略、分治策略、动静布局策略、线性规划策略、搜寻策略等。

这两条线索是互相独立的：

  • 对于同一个数据对象上不同的问题（如单源最短门路和多源最短门路)，就会用到不同的算法策略（如贪婪策略和动静布局策略）；
  • 对于齐全不同的数据对象上的问题(如排序和整数乘法)，兴许就会用到雷同的算法策略（如分治策略）。

我是 甜点 cc

酷爱前端，也喜爱专研各种跟本职工作关系不大的技术，技术、产品趣味宽泛且浓重，期待着一个守业机会。本号次要致力于分享集体经验总结，心愿能够给一小部分人一些渺小帮忙。

心愿能和大家一起致力营造一个良好的学习气氛，为了集体和家庭、为了我国的互联网物联网技术、数字化转型、数字经济倒退做一点点奉献。数风流人物还看中国、看今朝、看你我。

本文由 mdnice 多平台公布

退出移动版