本篇是学习了《趣学算法(第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)=1n=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)= 102334155fbn: 667.76msfbn2(40)= 102334155fbn2: 0.105msfbn3(40)= 102334155fbn3: 0.072ms

小结

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

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

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

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

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

我是 甜点cc

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

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

本文由mdnice多平台公布