人人都能看懂的时间复杂度和空间复杂度

你是怎么理解算法的呢？

简单说就是，同一个功能

• 别人写的代码跑起来占内存 100M，耗时 100 毫秒
• 你写的代码跑起来占内存 500M，耗时 1000 毫秒，甚至更多

所以

1. 衡量代码好坏有两个非常重要的标准就是：运行时间和占用空间，就是我们后面要说到的时间复杂度和空间复杂度，也是学好算法的重要基石
2. 这也是会算法和不会算法的攻城狮的区别、更是薪资的区别，因为待遇好的大厂面试基本都有算法

可能有人会问：别人是怎么做到的？代码没开发完 运行起来之前怎么知道占多少内存和运行时间呢？

确切的占内用存或运行时间确实算不出来，而且同一段代码在不同性能的机器上执行的时间也不一样，可是代码的基本执行次数，我们是可以算得出来的，这就要说到时间复杂度了

什么是时间复杂度

看个栗子

function foo1() {
  console.log("我吃了一颗糖")
  console.log("我又吃了一颗糖")
  return "再吃一颗糖"
}

调用这个函数，里面总执行次数就是 3 次，这个没毛病，都不用算

那么下面这个栗子呢

function foo2(n) {
  for (let i = 0; i < n; i++) {
    console.log("我吃了一颗糖")
  }
  return "一颗糖"
}

那这个函数里面总执行次数呢？根据我们传进去的值不一样，执行次数也就不一样，但是大概次数我们总能知道

let = 0               ：执行 1 次
i < n                 : 执行 n+1 次
i++                   : 执行 n+1 次
console.log("执行了")  : 执行 n 次
return 1              : 执行 1 次

这个函数的总执行次数就是 3n + 4 次，对吧

可是我们开发不可能都这样去数，所以根据代码执行时间的推导过程就有一个规律，也就是所有代码执行时间 T(n)和代码的执行次数 f(n) ，这个是成正比的，而这个规律有一个公式

T(n) = O( f(n) )

n 是输入数据的大小或者输入数据的数量
T(n) 表示一段代码的总执行时间
f(n) 表示一段代码的总执行次数
O  表示代码的执行时间 T(n) 和 执行次数f(n) 成正比

完整的公式看着就很麻烦，别着急，这个公式只要了解一下就可以了，为的就是让你知道我们表示算法复杂度的 O() 是怎么来的，我们平时表示算法复杂度主要就是用 O()，读作大欧表示法，是字母 O 不是零

只用一个 O() 表示，这样看起来立马就容易理解多了

回到刚才的两个例子，就是上面的两个函数

• 第一个函数执行了 3 次，用复杂度表示就是 O(3)
• 第二个函数执行了 3n + 4 次，复杂度就是 O(3n+4)

这样有没有觉得还是很麻烦，因为如果函数逻辑一样的，只是执行次数差个几次，像 O(3) 和 O(4)，有什么差别？还要写成两种就有点多此一举了，所以复杂度里有统一的简化的表示法，这个执行时间简化的估算值就是我们最终的时间复杂度

简化的过程如下

• 如果只是常数直接估算为 1，O(3) 的时间复杂度就是 O(1)，不是说只执行了 1 次，而是对常量级时间复杂度的一种表示法。一般情况下，只要算法里没有循环和递归，就算有上万行代码，时间复杂度也是 O(1)
• O(3n+4) 里常数 4 对于总执行次数的几乎没有影响，直接忽略不计，系数 3 影响也不大，因为 3n 和 n 都是一个量级的，所以作为系数的常数 3 也估算为 1 或者可以理解为去掉系数，所以 O(3n+4) 的时间复杂度为 O(n)
• 如果是多项式，只需要保留 n 的最高次项，O( 666n³ + 666n² + n )，这个复杂度里面的最高次项是 n 的 3 次方。因为随着 n 的增大，后面的项的增长远远不及 n 的最高次项大，所以低于这个次项的直接忽略不计，常数也忽略不计，简化后的时间复杂度为 O(n³)

这里如果没有理解的话，暂停理解一下

接下来结合栗子，看一下常见的时间复杂度

常用时间复杂度

O(1)

上面说了，一般情况下，只要算法里没有循环和递归，就算有上万行代码，时间复杂度也是 O(1)，因为它的执行次数不会随着任何一个变量的增大而变长，比如下面这样

function foo(){
    let n = 1
    let b = n * 100
    if(b === 100){
        console.log("开始吃糖")
    }
    console.log("我吃了1颗糖")
    console.log("我吃了2颗糖")
    ......
    console.log("我吃了10000颗糖")
}

O(n)

上面也介绍了 O(n)，总的来说 只有一层循环或者递归等，时间复杂度就是 O(n)，比如下面这样

function foo1(n) {
  for (let i = 0; i < n; i++) {
    console.log("我吃了一颗糖")
  }
}
function foo2(n) {
  while (--n > 0) {
    console.log("我吃了一颗糖")
  }
}
function foo3(n) {
  console.log("我吃了一颗糖")
  --n > 0 && foo3(n)
}

O(n²)

比如嵌套循环，如下面这样的，里层循环执行 n 次，外层循环也执行 n 次，总执行次数就是 n x n，时间复杂度就是 n 的平方，也就是 O(n²)。假设 n 是 10，那么里面的就会打印 10 x 10 = 100 次

function foo1(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log("我吃了一颗糖")
    }
  }
}

还有这样的，总执行次数为 n + n²，上面说了，如果是多项式，取最高次项，所以这个时间复杂度也是 O(n²)

function foo2(n) {
  for (let k = 0; k < n; k++) {
    console.log("我吃了一颗糖")
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log("我吃了一颗糖")
    }
  }
}

//或者下面这样，以运行时间最长的，作为时间复杂度的依据，所以下面的时间复杂度就是 O(n²)
function foo3(n) {
  if (n > 100) {
    for (let k = 0; k < n; k++) {
      console.log("我吃了一颗糖")
    }
  } else {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        console.log("我吃了一颗糖")
      }
    }
  }
}

O(logn)

举个栗子，这里有一包糖

这包糖里有 16 颗，沐华每天吃这一包糖的一半，请问多少天吃完？

意思就是 16 不断除以 2，除几次之后等于 1？用代码表示

function foo1(n) {
  let day = 0
  while (n > 1) {
    n = n / 2
    day++
  }
  return day
}
console.log(foo1(16)) // 4

循环次数的影响主要来源于 n/2 ，这个时间复杂度就是 O(logn) ，这个复杂度是怎么来的呢，别着急，继续看

再比如下面这样

function foo2(n) {
  for (let i = 0; i < n; i *= 2) {
    console.log("一天")
  }
}
foo2(16)

里面的打印执行了 4 次，循环次数主要影响来源于 i *= 2 ，这个时间复杂度也是 O(logn)

这个 O(logn) 是怎么来的，这里补充一个小学三年级数学的知识点，对数，我们看一张图

没有理解的话再看一下，理解一下规律

• 真数：就是真数，这道题里就是 16
• 底数：就是值变化的规律，比如每次循环都是 i*=2，这个乘以 2 就是规律。比如 1,2,3,4,5…这样的值的话，底就是 1，每个数变化的规律是+1 嘛
• 对数：在这道题里可以理解成 x2 乘了多少次，这个次数

仔细观察规律就会发现这道题里底数是 2，而我们要求的天数就是这个对数 4，在对数里有一个表达公式

a^b = n  读作以 a 为底,b 的对数=n，在这道题里我们知道 a 和 n 的值，也就是  2^b = 16 然后求 b

把这个公式转换一下的写法如下

log_an = b    在这道题里就是   log₂16 = ?  答案就是 4

公式是固定的，这个 16 不是固定的，是我们传进去的 n，所以可以理解为这道题就是求 log₂n = ?

用时间复杂度表示就是 O(log₂n)，由于时间复杂度需要去掉常数和系数，而 log 的底数跟系数是一样的，所以也需要去掉，所以最后这个正确的时间复杂度就是 O(logn)

emmmmm…..

没有理解的话，可以暂停理解一下

其他还有一些时间复杂度，我由快到慢排列了一下，如下表顺序

复杂度	名称
O(1)	常数复杂度
O(logn)	对数复杂度
O(n)	线性时间复杂度
O(nlogn)	线性对数复杂度
O(n²)	平方
O(n³)	立方
O(2n)	指数，一点数据量就卡的不行
O(n!)	阶乘，就更慢了

这些时间复杂度有什么区别呢，看张图

随着数据量或者 n 的增大，时间复杂度也随之增加，也就是执行时间的增加，会越来越慢，越来越卡

总的来说时间复杂度就是执行时间增长的趋势，那么空间复杂度就是存储空间增长的趋势

什么是空间复杂度

空间复杂度就是算法需要多少内存，占用了多少空间

常用的空间复杂度有 O(1)、O(n)、O(n²)

O(1)

只要不会因为算法里的执行，导致额外的空间增长，就算是一万行，空间复杂度也是 O(1)，比如下面这样，时间复杂度也是 O(1)

function foo(){
    let n = 1
    let b = n * 100
    if(b === 100){
        console.log("开始吃糖")
    }
    console.log("我吃了1颗糖")
    console.log("我吃了2颗糖")
    ......
    console.log("我吃了10000颗糖")
}

O(n)

比如下面这样，n 的数值越大，算法需要分配的空间就需要越多，来存储数组里的值，所以它的空间复杂度就是 O(n)，时间复杂度也是 O(n)

function foo(n) {
  let arr = []
  for (let i = 1; i < n; i++) {
    arr[i] = i
  }
}

O(n²)

O(n²) 这种空间复杂度一般出现在比如二维数组，或是矩阵的情况下

不用说，你肯定明白是啥情况啦

就是遍历生成类似这样格式的

let arr = [
  [1, 2, 3, 4, 5],
  [1, 2, 3, 4, 5],
  [1, 2, 3, 4, 5],
]