# 1. 概述与复杂度分析

> 本文是整个「数据结构与算法」系列的总纲。后续所有章节（顺序表、链表、栈、队列、树、图、哈希表、排序、查找）都建立在本章概念之上。

## 数据结构三要素

数据结构 = **逻辑结构** + **存储结构** + **数据的运算**。三者缺一不可：

| 要素       | 含义                                                   | 例子                     |
| ---------- | ------------------------------------------------------ | ------------------------ |
| 逻辑结构   | 数据元素之间的逻辑关系（与存储无关，是抽象出来的关系） | 线性结构、树形结构       |
| 存储结构   | 数据在计算机中的物理存储方式（如何把逻辑关系落地）     | 顺序存储、链式存储       |
| 数据的运算 | 施加在数据上的操作，如插入、删除、查找                 | 在顺序表中按下标插入元素 |

- 逻辑结构是「用什么关系组织数据」，存储结构是「怎么在内存里摆」，运算是「对这个结构能做什么」。
- 同一逻辑结构可以用不同存储结构实现，运算的实现效率随之不同。

## 四种逻辑结构

| 逻辑结构 | 特征                                               | 典型代表               |
| -------- | -------------------------------------------------- | ---------------------- |
| 集合结构 | 元素之间除了「同属于一个集合」外无其他关系         | 并查集、哈希集合       |
| 线性结构 | 元素之间一一对应，有唯一前驱和唯一后继（除了首尾） | 顺序表、链表、栈、队列 |
| 树形结构 | 一对多，一个根、多个分支，分层                     | 二叉树、堆、B 树       |
| 图状结构 | 多对多，任意两点之间都可能有关系                   | 有向图、无向图、网络   |

## 四种存储结构

| 存储结构 | 说明                                                     | 优点                         | 缺点                                     |
| -------- | -------------------------------------------------------- | ---------------------------- | ---------------------------------------- |
| 顺序存储 | 用一组连续的存储单元依次存放数据元素，逻辑相邻即物理相邻 | 随机存取、实现简单           | 插入删除需移动大量元素；需要大片连续空间 |
| 链式存储 | 用一组任意（不连续）的存储单元存放，借助指针表示逻辑关系 | 插入删除灵活、空间可动态分配 | 只能顺序存取；额外存储指针、空间开销大   |
| 索引存储 | 建立索引表，索引项指向数据元素                           | 查找速度快，便于按关键字检索 | 索引表本身占用空间，增删要维护索引       |
| 散列存储 | 根据元素的关键字直接计算出存储地址                       | 查找平均时间复杂度 O(1)      | 存在冲突（碰撞），需要处理冲突的策略     |

## 时间复杂度

- **定义**：算法执行时间随问题规模 n 增长的变化趋势，记为 **T(n)**。用**大 O 表示法**（算法的渐进时间复杂度）描述：`T(n) = O(f(n))`，表示 T(n) 的增长不慢于 f(n)。
- 只保留**最高阶项**，忽略常数系数与低阶项：例如 `T(n) = 3n² + 2n + 100` → `O(n²)`。
- **最坏 / 平均 / 最好** 三种情况：通常以**最坏时间复杂度**作为算法性能的保证。

### 常见复杂度量级排序（从小到大）

| 量级       | 名称       | 规模 10 时约执行 | 规模 100 时约执行 |
| ---------- | ---------- | ---------------- | ----------------- |
| O(1)       | 常数阶     | 1                | 1                 |
| O(log₂n)   | 对数阶     | 4                | 7                 |
| O(n)       | 线性阶     | 10               | 100               |
| O(n log₂n) | 线性对数阶 | 34               | 664               |
| O(n²)      | 平方阶     | 100              | 10 000            |
| O(n³)      | 立方阶     | 1 000            | 1 000 000         |
| O(2ⁿ)      | 指数阶     | 1 024            | 巨大              |
| O(n!)      | 阶乘阶     | 3 628 800        | 天文数字          |

> 排序关系：`O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)`

### 计算技巧

- 循环体执行次数 = 复杂度。`for(i=0;i<n;i++)` 内层固定操作 → O(n)。
- 两层嵌套循环（各自到 n）→ O(n²)；三层 → O(n³)。
- 循环变量**倍增/折半**（`i = i * 2` 或 `i /= 2`）→ O(log n)。
- 递归算法用**主定理**或画出递归树分析。

## 空间复杂度

- **定义**：算法运行所需**额外**存储空间随 n 增长的量级，记为 **S(n)**。
- 只统计**临时额外空间**，不包含输入本身占用的空间。
- 常见情况：原地操作（只用到常数额外变量）→ O(1)；递归深度为 n → O(n)。

## 各数据结构适用场景总览

| 数据结构 | 特点                                                                  | 适用场景                                         |
| -------- | --------------------------------------------------------------------- | ------------------------------------------------ |
| 顺序表   | 连续存储，支持 O(1) 随机存取；插入/删除需要移动元素，平均 O(n)        | 频繁**按下标访问**、表长基本固定、很少插入删除   |
| 链表     | 离散存储，插入/删除 O(1)（已知结点）；查找需要遍历 O(n)；额外指针开销 | 频繁插入/删除、表长动态变化、不知确切长度        |
| 栈       | 后进先出（LIFO），只能在栈顶操作                                      | 函数调用、括号匹配、表达式求值、撤销操作、DFS    |
| 队列     | 先进先出（FIFO），队尾入队、队头出队                                  | 任务调度、打印队列、广度优先搜索 BFS、缓冲       |
| 树       | 层次关系，一对多；二叉树、二叉搜索树、堆等变体                        | 文件系统目录、表达式树、优先队列（堆）、查找树   |
| 图       | 多对多关系，顶点+边                                                   | 社交网络、地图导航（最短路径）、网络拓扑、状态机 |
| 哈希表   | 关键字 → 地址，平均 O(1) 查找                                         | 快速检索/去重、缓存、字典映射（键值对）          |

## 复杂度计算示例

### C 示例：两层循环求和

```c
#include <stdio.h>

// 计算 1*1 + 1*2 + ... + n*n 的累加
// 内层循环执行次数：n*(n+1)/2 次 -> 时间复杂度 O(n^2)
int sum(int n) {
    int total = 0;                    // O(1) 额外空间，空间复杂度 O(1)
    for (int i = 1; i <= n; i++)      // 外层 n 次
        for (int j = 1; j <= n; j++)  // 内层 n 次
            total += i * j;
    return total;
}

int main(void) {
    int n = 5;
    printf("sum(%d) = %d\n", n, sum(n));
    return 0;
}
```

### Python 示例：折半（对数阶）

```python
# 每次循环 i 翻倍，只需 log2(n) 次 -> 时间复杂度 O(log n)
def count_steps(n: int) -> int:
    steps = 0
    i = 1
    while i < n:
        i = i * 2
        steps += 1
    return steps

if __name__ == "__main__":
    n = 1000
    print(f"n={n} 时循环次数: {count_steps(n)}")  # 约 10 次
```

## 系列导航

| 章节 | 主题             | 复杂度主线                           |
| ---- | ---------------- | ------------------------------------ |
| 本页 | 概述与复杂度分析 | O(1) ~ O(n!) 量级                    |
| 2    | [[2.顺序表]]     | 随机存取 O(1)，插入删除 O(n)         |
| 3    | [[3.单链表]]     | 插入删除 O(1)（已知结点），查找 O(n) |
| 4    | [[4.双链表]]     | 可双向遍历，前插 O(1)                |
| 5    | [[5.循环链表]]   | 从尾部到头 O(1)，遍历终止条件特殊    |

> 阅读建议：先掌握本页的复杂度分析方法，再按 2 → 5 的顺序学习线性表，重点对比「顺序存储 vs 链式存储」的取舍。