# 通过 JavaScript 学习算法复杂度

```1const smArr = [5, 3, 2, 35, 2];
2
3const bigArr = [5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2];
```

## 什么是 Big O 符号？

Big O 表示法是用来表示随着数据集的增加，计算任务难度总体增长的一种方式。尽管还有其他表示法，但通常 big O 表示法是最常用的，因为它着眼于最坏的情况，更容易量化和考虑。最坏的情况意味着完成任务需要最多的操作次数；如果你在一秒钟内就能恢复打乱魔方，那么你只拧了一圈的话，不能说自己是做得最好的。

## O(1)

``` 1const a1 = performance.now();
2smArr.push(27);
3const a2 = performance.now();
4console.log(`Time: \${a2 - a1}`); // Less than 1 Millisecond
5
6
7const b1 = performance.now();
8bigArr.push(27);
9const b2 = performance.now();
10console.log(`Time: \${b2 - b1}`); // Less than 1 Millisecond
```

## O(n)

```1const a1 = performance.now();
2smArr.forEach(item => console.log(item));
3const a2 = performance.now();
4console.log(`Time: \${a2 - a1}`); // 3 Milliseconds
5
6const b1 = performance.now();
7bigArr.forEach(item => console.log(item));
8const b2 = performance.now();
9console.log(`Time: \${b2 - b1}`); // 13 Milliseconds
```

## O(n^2)

``` 1const a1 = performance.now();
2smArr.forEach(() => {
3    arr2.forEach(item => console.log(item));
4});
5const a2 = performance.now();
6console.log(`Time: \${a2 - a1}`); // 8 Milliseconds
7
8
9const b1 = performance.now();
10bigArr.forEach(() => {
11    arr2.forEach(item => console.log(item));
12});
13const b2 = performance.now();
14console.log(`Time: \${b2 - b1}`); // 307 Milliseconds
```

## O(log n)

``` 1const sort = arr => {
2  if (arr.length < 2) return arr;
3
4  let pivot = arr[0];
5  let left = [];
6  let right = [];
7
8  for (let i = 1, total = arr.length; i < total; i++) {
9    if (arr[i] < pivot) left.push(arr[i]);
10    else right.push(arr[i]);
11  };
12  return [
13    ...sort(left),
14    pivot,
15    ...sort(right)
16  ];
17};
18sort(smArr); // 0 Milliseconds
19sort(bigArr); // 1 Millisecond
```

## O(n!)

``` 1const factorial = n => {
2  let num = n;
3
4  if (n === 0) return 1
5  for (let i = 0; i < n; i++) {
6    num = n * factorial(n - 1);
7  };
8
9  return num;
10};
11factorial(1); // 2 Milliseconds
12factorial(5); // 3 Milliseconds
13factorial(10); // 85 Milliseconds
14factorial(12); //  11,942 Milliseconds
```

## 结束语

2020年京程一灯全新课程体系即将推出，请保持关注。