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
}以上代码没有循环，从对象取一个属性算一次计算量，做加分算一次计算量，都是属于常量级别的数量级，即O（1）。
O（n）代码示例
function fn(arr = []) {
// O(n)
for (let i = 0; i < arr.length; i++) {
console.info(arr[i])
}
}以上代码的计算量和数组长度成正比，长度是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])
}
}
}以上代码并无实际意义，只谈论计算量，这里是双层循环，当外层循环一次，内层循环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]
// ...
}在这里这种平铺直叙的给变量分配一个空间，它的复杂度就是O（1）。
O(n) 代码示例
function fn(arr = []) {
const arr2 = [];
for(let i = 0; i < arr.length; i++) {
arr2[i] = arr[i] + 10
}
// ...
}这里可以看出定义的数组arr2的空间大小与arr的长度成正比的关系，所以这里的空间复杂度是O(n)。
程序员必须掌握算法复杂度
- 如果你没有复杂度的概念和敏感度，写程序是非常危险的
- 例如，代码功能测试正常，但数量大了，程序就会崩溃
- 对应前端开发，尤其注重时间复杂度（前端：重时间，轻空间）
