「算法与数据结构」时间与空间复杂度

写在前面

可能有些人会吐槽，学算法有什么用，顶多就是去面试大厂的时候能用上，大厂面试算法也只是强中筛强的一个敲门砖而已，我又不去面大厂，不用学它，真的是这样吗？

肯定不是，在计算机行业发展，不管是前端亦或是后端，算法都是进阶的一个绊脚石，可以说不会算法永远也成不了一个合格的高级工程师，想要进大厂确实要会些算法，但是它并不只是为了面试，它和我们的程序是息息相关的，有人说前端不需要算法？你把大名鼎鼎的 虚拟DOM (Virtual DOM) 置于何地，它就是 算法与数据结构 的一种体现，可能又有人会说了，我又不写虚拟DOM。。。嗯，那你总想要赚钱吧，走技术路线想拿高薪，算法是基石

网上有很多算法文章以及课程，说 7 天学会算法数据结构，30 天掌握算法与数据结构等等等等，别傻了，算法没有捷径，只能靠我们一点一点累积，你要做的首先就是相信自己不是天才，其次是每天坚持刷题，时间紧可以一周刷四五题，最好速度是每天一题，后期时间充裕或者熟练了甚至可以一天刷几题，即使很聪明的人在一段时间不接触算法后，还是会忘掉，所以重要的是持续下去

接下来我们来从零开始学习算法吧，如果你未曾刷过算法，这篇文章会带你了解什么是算法，什么是数据结构，在刷算法的同时，我们要明确自己的解法是否足够优质，而判断优质解发会通过时间以及空间两个维度来体现，本文更会重点介绍，这些都是刷算法之前需要必备的知识，如果能为你的算法之路带来启蒙，那真是太棒了，十分荣幸，如果你已经了解了这些知识，那么不妨快速阅读下，看看是否能为你的算法知识做些扩充，当然如果有错误的地方，你也可以为我指引，更是十分荣幸

什么是数据结构

数据结构其实就是是程序存储组织数据的方式，一个数据结构是由程序中的数据元素按照某种逻辑关系组织起来的，是若干个数据元素的组合

数据结构是程序中处理数据的基本单位，在程序中作为一个整体来使用

例如一个数字 1 或者一个字符 A，它是一种数据结构

例如一个日期 2020年12月14日，它由年月日这 3 种格式组成，也是一种数据结构

例如一个数组 [1, 'a', '2020年12月14日']，它是由数字、字符、日期格式组合而成，也是一种数据结构

通俗来说，用一定格式组成的数据都是数据结构，我们比较常见的数据结构有字符串、数组、对象、堆、栈、链表、树、哈希表等等，你可能对着其中的一些数据结构并不了解，不要担心，你并不需要立刻知道它们都是什么，对于前端来说，我们使用 JavaScript 这个令我们又爱又恨的语言，它本身就存在的数据结构很少，那么对于像链表、树等等这些结构都是通过对象来模拟的，这点要先知道

在许多程序设计当中，数据结构的选择是一个基本的设计考虑因素，系统实现的困难程度和系统构造的质量都严重依赖于是否选择了最优的数据结构，选择最优的数据结构能够有效的提高运行的效率和节约存储空间的使用，但是要知道，没有十全十美的数据结构，每种数据结构都有局限性同样也有优点，要根据需求来选择合适的数据结构

什么是算法

什么是算法，我们都知道 1+2+3=6，为什么等于 6 呢，你可能会说，1 加 2等于 3，两个 3 相加等于 6，这是小学生都会的数学常识，它就是广义上的算法

算法其实就是解决一个问题的完整步骤描述，是指完成一个任务准确而完整的步骤描述

算法的设计很多时候需要取决于数据结构，而算法的实现更依赖于采用的数据结构

提出一个问题的算法是一个从抽象到具体的过程

• 分析问题，选择数据结构，得出初步的解决方法

• 将解决方法合理地拆分，整理成许多步骤

• 为重复的步骤选择合理的循环变量

• 使用易转化为程序实现的自然语言简练地描述算法

了解了什么是算法之后，我们来看时间和空间复杂度，衡量不同算法之间的优劣我们通常从两个维度来考究

• 时间维度：指执行代码所消耗的时间，即时间复杂度
• 空间维度：指执行代码所消耗的空间，即空间复杂度

接下来就开始逐步剖析时间和空间复杂度了，先说时间复杂度

时间复杂度

在说时间复杂度之前，我们首先要理解一个概念即代码执行次数，也可称之为语句频度或时间频度，用 T(n) 表示

我们用例子来一步一步阐述，首先我们来看函数 fn1

function fn1(){
  console.log("句末")
  console.log("isboyjc")
}

我们来看这个函数中的语句会执行多少次

很明显此函数内部只有两个语句，即 console.log("句末") 和 console.log("isboyjc")，那么我们说这个函数体内代码执行次数是 2

我们再来看函数 fn2

function fn2(n){
  for(let i = 0; i < n; i++){
    console.log("句末")
  }
}

我们先来看函数 fn2 中有几条可执行语句

let i = 0
i < n
i++
console.log("句末")

我们假设 n = 3，然后依次带入进去，看看各个执行语句执行了多少次

let i = 0 此条声明语句只在第一次 for 循环声明时执行 1 次

i < n 此条语句执行次数根据形参 n 的大小变化，n = 3 时，即 i=0,i=1,i=2,i=3 时会执行，即此条语句执行次数为 n + 1 次

i++ 此条语句执行次数也是根据形参 n 的大小变化，n = 3 时，即 i=0,i=1,i=2 时会执行，即 n 次

console.log("句末") 此条语句执行次数还是根据形参 n 的大小变化，n = 3 会执行 3 次，那么此语句在函数内部即会执行 n 次

1 + (n + 1) + n + n = (3n + 2)

那么函数 fn2 内共执行 3n + 2 次

一段代码的总执行次数我们通常会用 T(n) 来表示，那么调用一次上面 fn1/fn2 两函数的总执行次数即

T(n) = 2	// fn1
T(n) = 3n + 2 	// fn2

上面的 n，指的是为问题的规模，即输入数据的大小或者说数量，你也可以简单的理解为 T 就是函数本身，n 就是参数，也就是说

函数 fn1 任何情况下执行次数都为 2

函数 fn2 的总执行次数会根据 n 的大小变化而产生一个变化

我们思考一下，我们可以使用一段代码的执行总次数来衡量执行速度吗？

答案当然是不行的，当代码行数比较多的时候，我们一条一条的数来计算执行总次数太麻烦了，例如函数中套用函数时、循环中套用循环时，想要精确计算执行次数都是非常麻烦的

所以，在算法中，我们一般用 T(n) 简化后的估算值来表达代码执行的速度，通常我们用大些字母 O 来表示，即大 O 表示法，由于是估算，它表示的是代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度

明确了这个概念以后，我们就可以来算时间复杂度了，还是用上面 fn1/fn2 两函数例

// fn1
T(n) = 2

// fn2
T(n) = 3n + 2

首先我们来看函数 fn1，它的执行总次数为 2，一个 常数(常数级)，也就是说此函数无论何时它的总执行次数都是 2，是一个不变的值，那么我们使用时间复杂度 O 来表示时直接估算为 1 就可以，即时间复杂度为 O(1)

我们再来看函数 fn2 ，它的执行次数 T(n) 是 3n + 2 即 常数*n + 常数，这里我们完全可以看成 常数*n 和 +常数 两部分，随着 n 的增大，只有前一个部分会有变化，后面是不变的，所以在表示时间复杂度时就可以忽略后面不变的常数，即 常数*n，而 常数*n 中过的常数我们也可以直接当做 1，或者说忽略掉这个作为系数的常数，那么最终可以得出函数 fn2 的时间复杂度为 n，即 O(n)

PS：晓得可能有人把数学知识还给老师了，所以解释下

常数： 常数就是指平常的数值，可简单的理解为固定不变的数值

系数： 系数指代数式的单项式中的数字因数，例如 a = 1 * a ，则它的系数为 1，2b = 2 * b ，则它的系数为 2

我们再来举个例子，如下面这个多项式代指一个函数的 T(n)，求它的时间复杂度

T(n) = 10n^4 + 100n^2 + 1000

其实，对于多项式，我们只需要保留最高次项就行了，也就说，保留 n 的最高次方数就可以了，这个例子中保留的也就是 n 的 4 次方，系数和常数皆可以忽略，最终得到的时间复杂度即为 O(n^4)

结论：

T(n) 为常数时，时间复杂度为 O(1) ，反之时间复杂度为 O(保留T(n)的最高次项并去掉最高次项的系数)

接下来，我们看几个例子来判断下几段代码的时间复杂度

例1：

function fn01(){
  console.log("你看这是啥")
  console.log("这是一个输出")
  console.log("哈哈哈")
  let a = 1
  return a
}

上面这个函数 fn01 中只有一条条的语句，共执行 5 次，毫无变化，时间复杂度即 O(1) ，此为常数级时间复杂度

例2：

function fn02(n){
  for(let i = 0; i < n; i++){
    console.log("这是一个输出?")
  }
}

如上，函数 fn02 同上文中的例子 fn2，一个循环，时间复杂度即为 O(n) ，此为线性级时间复杂度

例3：

function fn03(n){
  for(let i = 0; i < n; i++){
    console.log("外层循环")
    for(let j = 0; j < n; j++){
      console.log("内层循环")
    }
  }
}

这个题和上面就不太一样了，我们先单独看内部的循环，内部循环大概会执行 n 次，再来看外部循环又会执行 n 次，最终也就是 n * n = n^2，即函数 fn03 的时间复杂度为 O(n^2) ，此为平方级时间复杂度，如果是三层循环也就是时间复杂度为 O(n^3) 时，即立方级时间复杂度

从这里我们就可以看出来，一段代码有多少层循环，时间复杂度就是 n 的多少次方，所以尽量避免多层循环嵌套

例4：

我们再来看下面这个函数 fn04

function fn04(n){
  for(let i = 0; i < n; i++){
    console.log("外层循环")
    for(let j = 0; j < n; j++){
      console.log("内层循环")
    }
  }
  
  for(let i = 0; i < n; i++){
    console.log("哈哈哈")
  }
}

此函数中有一个双循环，有一个单循环，即执行次数大概是 n^2 + n，根据我们上面说的保留最高次项，那么函数 fn04 的时间复杂度即为 O(n^2)

例5：

算法中肯定不只是上面那种寻常的循环，再来看下面这一个

function fn05(n){
  for(let i = 0; i < n; i++){
    console.log("外层循环")
    for(let j = i; j < n; j++){
      console.log("内层循环")
    }
  }
}

其实遇到这种，我们直接带入进去试一试即可知其规律

当 i = 0 时，里层循环会执行 n 次

当 i = 1 时，里层循环会执行 n - 1 次

当 i = 2 时，里层循环会执行 n - 2 次

当 i = 3 时，里层循环会执行 n - 3 次

这个时候我们就发现了规律，每当 i 增加 1，里层循环就少执行 1 次，那么就简单了

当 i = n - 2 时，里层循环会执行 2 次

当 i = n - 1 时，里层循环会执行 1 次

最终我们把 n 个里层循环的执行次数相加即可得出最终的一个不精确的总执行次数

T(n) = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1

如上，这是一个等差数列，嗯，晓得，会补充

如果一个数列从第二项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列，而这个常数叫做等差数列的公差，公差常用字母 d 表示

例如：1,3,5,7,9……（2n-1) ，等差数列 S(n) 的通项公式为：S(n) = S1 + (n-1) * d，前 n 项和公式如下

S(n) = n*S1 + n*(n - 1)*d/2

// 或

S(n) = n*(S1 + Sn)/2

如此我们计算结果就成，我们上面的数列中，公差 d 为 -1，带入公式即可，第二个公式简单，用第二个好了，计算结果都是一样的

// n*(S1 + Sn)/2

n*(n + 1)/2 = (n^2 + n)/2 = (1/2)n^2 + (1/2)n

最终我们得到了 (1/2)n^2 + (1/2)n ，按照上文中取最高次项去掉系数，即时间复杂度为 O(n^2)

例6：

再来看一个例子

function fn06(n){
  for(let i = 1; i < n; i *= 2){
    console.log("isboyjc")
  }
}

还是老样子，如果你不晓得怎么看，可以先带入几个参数试一下，看一看规律

我们可以分别使用 n=2, n=4, n=8, n=16，观察其循环中打印次数，当然你也可以直接运行一下代码，过程不过多阐述了，我们直接看结果

n=2		时打印1次 T(n)=1
n=4		时打印2次 T(n)=2
n=8		时打印3次 T(n)=3
n=16 		时打印4次 T(n)=4

对于执行次数产生主要影像的就是循环语句中的 i*=2，每次循环 i 都会变成自身的两倍，仔细观察我们就可以得出这样一个规律性结果

n=2		时打印1次 T(n)=1 // 2^1 = 2
n=4		时打印2次 T(n)=2 // 2^2 = 4
n=8		时打印3次 T(n)=3 // 2^3 = 8
n=16 		时打印4次 T(n)=4 // 2^4 = 16

根据上面的规律我们不难发现，那么2^执行次数=n，即 2^T(n)=n ，我们求 T(n)，调个就行了，也就是以 2 为底 n 的对数，即 T(n)=log_2 n

PS：又来补数学了

对数： 假如 a^n=b，即 a 的 n 次方等于 b，我们求 n 的值，那么这里为了方便表示就可以写成 log_a b，即以 a 为底 b 的对数，a 是底数，b 是真数，而 n 就是对数

你可能会在纠结为什么只观察循环中的打印次数而不计算其所有的执行次数，原因上面也说过了，这些固有的常数及系数完全可以忽略，好吧，我们再最后推一遍

中间输出为 log_2 n 次，let i = 1 只会执行一次，i<n 会执行 log_2 n + 1 次，i*=2 也会执行 log_2 n 次，加起来就是 log_2 n + log_2 n + 1 + log_2 n，即 3log_2 n + 2，除去系数 3 和常数 2，我们得出了 log_2 n ，在时间复杂度的计算中 log 的底数也是可以省略的，所以最终函数 fn06 的时间复杂度为 O(log n) ，也就是对数级时间复杂度

例7：

最后在给大家来一个例子吧

function fn07(n,m){
  for(let i = 0; i < n; i++){
    while(j < m){
      console.log("你看懂了吗")
      j = j * 2
    }
  }
}

如上图，此函数有两个参数，对应了里外两个循环，我们先从内部循环看起，眼熟吗？其实内部循环和上题函数 fn06 中的循环是一样的，只是一个用的 for ，一个用的 while，上题中的时间复杂度我们就不再叙述了，那么内层循环时间复杂度为 O(log n)

我们再来看外层循环，也是上面解释过的，单看外层循环时间复杂度是 O(n)

两个循环是嵌套关系，相乘就可以了，所以函数 fn07 的时间复杂度即为 O(n*log n) ，也就是线性对数级时间复杂度

正如此函数输出，你看懂了吗？

码字太累，看个图吧：

找了一张网图（侵删），使用图表来更加清晰的展示了常见的时间复杂度曲线

如上图，横坐标为 n ，可以看到，不同时间复杂度随着 n 的增大操作次数或者说执行时间的递增趋势

常见的时间复杂度量级有

• 常数级 O(1)
• 对数级 O(log n)
• 线性级 O(n)
• 线性对数级 O(n*log n)
• 平方级 O(n^2)
• 立方级 O(n^3)
• K次方级 O(n^k)
• 指数级 O(2^n)

上面从上到下依次时间复杂度越来越大，执行效率越来越低，大部分常用的在上面的图表中都有展示

所以在程序或是刷题中，我们应该尽量使用低时间复杂度的方法

时间复杂度就到此为止了，我们也列举了常见的时间复杂度，接下来我们来看看空间复杂度

空间复杂度

空间复杂度其实就是对一个算法或者说一段代码在运行过程中占用存储空间大小表达方式

我们上面讲过了时间复杂度，那么再来说空间复杂度会简单的很多

空间复杂度也就是 S(n) ，它同样会用大O表示法来表示，我们直接上例子

例1：

function fn001(n){
  for(let i = 0; i < n; i++){
    console.log("空间复杂度")
  }
}

首先，我们知道，空间复杂度和存储空间有关，而存储空间是由什么决定的，肯定是声明的变量啊，我们直接来找函数 fn001 中的变量声明，只有一个 i ，也就是说此函数只有开辟了一块空间供 i 使用，那么空间复杂度 S(n) 即为 O(1) ，你可能会说 i 不是一直在变吗，是的它是在变，但是不管怎么变，它还是一个数字，占用空间大小都一致

空间复杂度和时间复杂度一样，当代码里声明的变量是一个常量，不会根据传入值的变化而变化，那么也它的空间复杂度是 O(1)

例2：

function fn002(n){
  let arr = []
  while(n--){
    arr.push(n)
  }
}

这个例子中我们声明了一个数组，我们知道数组中是可以存各种类型的，在循环中，我们根据 n 的大小向数组 arr 中 push 元素，所以，n 多大，数组就有多少元素，就占用了多少空间，所以空间复杂度S(n) = O(n)

空间复杂度小结

空间复杂度里，只列出了两个例子，是因为一般情况下，我们用不到其他的，空间复杂度一般只会是 O(1)/O(n)/O(n^2)，其它的很少见，当然也有，我们在知道了时间复杂度再分析空间复杂度也很好分析，就不过多赘述了

关于分析空间复杂度，其实我们直接从声明的变量入手就可以，看函数体内声明的变量根据传入值的变化而变化来分析

另外，这里我们没有列举递归情况，请注意，递归就是函数套函数，像俄罗斯套娃一样的，这中间其实有一个问题，我们知道，递归函数，每层递归里都会开辟一个递归栈，每次递归产生的变量等空间消耗都会存在递归栈中，这也是一个空间，不管你有没有声明变量，只要递归了递归栈它都存在，也就是说只要存在递归的情况，基本上最少的空间复杂度也是 O(n) 了，所以我们尽可能的在能使用迭代的情况下就不使用递归

时间 VS 空间

开头我们说了，评价一个算法的效率我们主要是从它的时间和空间两个维度看，但是，通常我们在算法中，时间和空间就是鱼和熊掌的关系，这时候可能一道算法题有两种解法，一种时间复杂度低，但空间复杂度稍高，另一种则反之

这个时候怎么办呢？细品就知道了，在开发中，我们一般都是时间优于空间的，你想啊，一个程序，用户不会关心的占用了多少内存，但是他会关心你这个程序他在使用时的执行速度，况且，空间也就是磁盘，现阶段磁盘我们可以花钱扩容，时间上就没这么简单了，所以某些相对的情况下，空间换时间是可以令人接受的

虽说空间换时间可行，但也不能一味的空间换时间，我们还是要尽可能降低两个维度的复杂度，少数对立情况下，可空间换时间

我们在刷算法的时候，不是刷完了就完事了，我们还要去分析我们的题解对应的时间及空间复杂度，可以分析多种题解之间的复杂度，对比找出最优解

在面试的时候，假如面试官给你一道算法题，当你知道好几种解法的时候，完全可以很装B的问一下，您喜欢时间至上还是空间至上呢，我都能解，奥利给，说完他就会让你都写了?

开个玩笑哈，面试的时候尽量写出多种解法并给面试官解释各种解法时间及空间复杂度的不同，怎么说？就很棒

最后

此文介绍算法一些理论基础，理解之后就可以刷题了，推荐按照数据结构类型来每天刷一题

建议上班无聊时刷题，上班摸鱼水群不如摸鱼刷道算法，百利无一害，坚持每天刷题吧，加油

GitHub算法仓库，使用JavaScript从零更算法题/文字/视频 题解ing，来关注吧 ? GitHub传送门

此文及以后刷的每题都有视频版，主要是为了跟思路讲一遍手写一下，讲的可能不好，详见 ? B站传送门

看到这里了，来个三连吧，如有错误请指正，也欢迎大家关注公众号「不正经的前端」，和算法群的朋友们组团刷算法，效率更高