1、什么是复杂度？

1、复杂度理解

• 程序执行时需要的计算量和内存空间（和代码是否简洁无关）

• 复杂度是数量级 （方便记忆、推广），不是具体的数字

• 一般针对一个具体的算法，而非一个完整的系统

2、时间复杂度 - 程序执行时需要的计算量（CPU）

• O(1) 一次就够 （数量级）
• O(n) 和传输的数据量一样 （数量级）
• O(n^2) 数据量的平方 （数量级）
• O(logn) 数据量的对数 （数量级）
• O(n * logn) 数据量 * 数据量的对数 （数量级）

O（1）代码示例

function fn(obj = {}) {
    // O(1)
    return obj.a + obj.b + obj.c // 4-5
}
1
2
3
4

以上代码没有循环，从对象取一个属性算一次计算量，做加分算一次计算量，都是属于常量级别的数量级，即O（1）。

O（n）代码示例

function fn(arr = []) {
    // O(n)
   for (let i = 0; i < arr.length; i++) {
       console.info(arr[i])
   }
}
1
2
3
4
5
6

以上代码的计算量和数组长度成正比，长度是10，计算量就是10，所以这里的计算量是O（n）。

O（n^2）代码示例

function fn(arr = []) {
    // O(n^2)
   for (let i = 0; i < arr.length; i++) {
       for (let j = 0; j < arr.length; j++) {
           console.info(arr[j])
       }
   }
}
1
2
3
4
5
6
7
8

以上代码并无实际意义，只谈论计算量，这里是双层循环，当外层循环一次，内层循环n次；当外层循环n次，内层循环n * n次，所以这里的计算量是O（n^2）。

O（logn）代码示例

其实就是一个二分计算

O（n * logn） 代码示例

就是一个循环嵌套一个二分运算

3、空间复杂度 - 程序执行时需要的内存空间

• O(1) 有限的、可数的空间 （数量级）
• O(n) 和输入的数量级相同的空间 （数量级）

O(1) 代码示例

function fn (arr = []) {
    // O(1)
    const a = arr[1]
    const b = arr[2]
    // ...
}
1
2
3
4
5
6

在这里这种平铺直叙的给变量分配一个空间，它的复杂度就是O（1）。

O(n) 代码示例

function fn(arr = []) {
    const arr2 = [];
    
    for(let i = 0; i < arr.length; i++) {
        arr2[i] = arr[i] + 10
    }
    // ...
}
1
2
3
4
5
6
7
8

这里可以看出定义的数组arr2的空间大小与arr的长度成正比的关系，所以这里的空间复杂度是O(n)。

程序员必须掌握算法复杂度

• 如果你没有复杂度的概念和敏感度，写程序是非常危险的
• 例如，代码功能测试正常，但数量大了，程序就会崩溃
• 对应前端开发，尤其注重时间复杂度（前端：重时间，轻空间）