## 先来看下度娘的算法复杂度百科
算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）
## 时间复杂度的计算方法
1. 找到基本语句，通常是循环；
2. 保留最高次幂且忽略系数；
3. 用大O符号表述。
常见的算法时间复杂度排列为：
O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < ... < O(2^n) < O(3^n) < ... < O(n!)
### 例子： 时间复杂度 O(1)
```js
function fun(n) {
console.log('Hello, World!');
}
// O(1)
```
### 例子： 时间复杂度 O(n)
```js
function fun(n) {
for (var i = 0; i < n; i++) { // 循环次数为 n
console.log('Hello, World!'); // 循环体复杂度为 O(1)
}
}
// O(n*1) -> O(n)
```
### 例子： 时间复杂度 O(n^2)
```js
function fun(n) {
for (var i = 0; i < n; i++) { // 循环次数为 n
for (var j = 0; j < n; j++) { // 循环次数为 n
console.log('Hello, World!'); // 循环体复杂度为 O(1)
}
}
}
// O(n*n*1) -> O(n^2)
```
### 例子： 保留最高次幂且忽略系数
```js
// 保留最高次幂且忽略系数
function fun(n) {
for (var i = 0; i < n; i++) { // 循环次数为 n
console.log('Hello, World!'); // 循环体复杂度为 O(1)
}
for (var i = 0; i < n; i++) { // 循环次数为 n
for (var j = 0; j < n; j++) { // 循环次数为 n
console.log('Hello, World!'); // 循环体复杂度为 O(1)
}
}
for (var i = 0; i < n; i++) { // 循环次数为 n
for (var j = 0; j < n; j++) { // 循环次数为 n
console.log('Hello, World!'); // 循环体复杂度为 O(1)
}
}
}
// O(n, 2n^2) -> O(n^2)
```
### 例子： 概率
```js
function fun() {
while (Math.random() < 0.5) { // Math.rendom [0,1) 期望值为2
console.log('Hello, World!'); // 循环体复杂度为 O(1)
}
return true;
}
// O(2*1) -> 忽略系数2 -> O(1)
```
## 空间复杂度计算方法
空间复杂度是指执行这个算法所需要的内存空间。
常见的空间复杂度只有 O(1)、O(n)、O(n^2)。
### 例子： 空间复杂度 O(1)
```js
function fun(n) {
var num = n + 1;
return num;
}
// O(1)
```
### 例子： 空间复杂度 O(n)
```js
function fun(n) {
var arr = new Array(n).fill('0');
return arr;
}
// O(n) 数组的长度根据 n 变化
```
### 例子： 空间复杂度 O(n^2)
```js
function fun(n) {
var arr = [];
for (var i = 0; i < n; i++) {
arr[i] = [];
for (var j = 0; j < n; j++) {
arr[i][j] = j;
}
}
return arr;
}
// O(n^2)
```
## JavaScript常见算法的时间复杂度和空间复杂度
| Name | Best | Average | Worst | Memory | Stable |
|-|-|-|-|-|-|
|冒泡排序|n|n^2|n^2|1|Yes|
|选择排序|n^2|n^2|n^2|1|No|
|插入排序|n|n^2|n^2|1|Yes|
|堆排序|n*log(n)|n*log(n)|n*log(n)|1|No|
|归并排序|n*log(n)|n*log(n)|n*log(n)|n|Yes|
|快速排序|n*log(n)|n*log(n)|n^2|log(n)|No|
