# 数据结构（一）时间复杂度与空间复杂度


## 开头

好记性不如烂笔头，在这里记录下学习数据结构与算法之美的笔记

## 简述

- 数据结构指的是‘一组数据的存储结构’，算法指的是’操作数据的一种方法‘。
- 数据结构是为算法服务的，算法要作用在特定的数据结构之上。

## 正片

### 复杂度分析

#### 时间复杂度 （大 O 复杂度表示法）

算法的执行效率，粗略的讲，就是算法代码的执行时间。

```js
const (n) => {
  const sum = 0;
  const i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  };
  return sum
}
```

假设每行代码执行的时间都一样，为 o,那么

第 2, 3 行分别需要一个 o 的执行时间；

第 4, 5 行都运行了 n 次，所以需要 2 个 n\* o 的执行时间；

这段代码的总执行时间就是：`（2n + 2）* o`。

可以看出，每行代码的执行次数越多，总执行时间 T(n)就越高。按照这个思路，再看一段代码

```js
const (n) => {
  const sum = 0;
  const i = 1;
  for (; i <= n; ++i) {
    const j = 1;
    for (; j <= n; ++j) {
      sum = sum + i + j;
    }
  };
  return sum
}
```

第 2、3、5 行需要一个 o 的执行时间；

第 4、5 行执行了 n 遍，需要 2 个 n \* o 的执行时间；

第 7、8 行执行了 n^2 遍，需要 2 个 n^2 \* o 的执行时间；

总执行时间为`(2n^2 + 2n + 3) * o`。

通过推导，得到一个公式`T(n) = O(f(n))`
t(n)表示代码的执行时间，f(n)表示代码执行次数的总和，所以，第一个例子中的 T(n) = `O(2n + 2)`和第二个例子的 T(n) = `O(2n^2 + 2n + 3)`。这就是大 O 时间复杂度表示法，他并不能具体表示代码的真正执行时间，而是表示代码执行时间`随数据规模增长的变化趋势`。
其中，f(n)中的低阶、常量、系数、三部分对增长趋势不产生绝对影响（在（2n^2 + 2n + 3）中，低阶是 2n、常量是 3、系数是 2），所以都可以省略，我们只需要记录一个最大量级就可以，因此，前两个例子的事件复杂度可以记为`T(n) = O(n); T(n) = O(n^2)`。

#### 几种常见的时间复杂度

（按数量级排列）

1. 常量阶： O(1)

```js
// 只要代码的执行时间不随n的增大而增大，这样代码的时间复杂度都记作O(1)
const func = (n) => {
  const a = 1;
  const b = 2;
  return a + b;
};
```

2. 对数阶： O(log n)

```js
let i = 1;
while (i <= n) {
  i = i * 2;
}
```

3. 线性阶： O(n)
4. 线性对数阶： O(n \* log n)
5. 平方阶： O(n^2)、立方阶： O（n^3）......
6. 指数阶： O(2^n)
7. 阶乘阶： O(n!)

#### 空间复杂度

与时间复杂度同理，表示算法的存储空间与数据规模的增长关系。

#### 常见的空间复杂度

O(1)、O(n)、o(n^2)