---
title: "01-绪论与复杂度"
created: 2026-08-29
tags:
  - 基础与理论
  - 数据结构
  - "408"
---

# 01 绪论与复杂度

> 📚 本文是 [[00-数据结构总览|数据结构]] 的第 1 篇，相关系列见 [[00-基础与理论|基础与理论]]。

磨刀不误砍柴工：这一篇解决两个元问题——**结构怎么分类**（逻辑 vs 存储），以及**程序怎么算快慢**（复杂度分析）。后者是后面每一篇都会用到的"度量衡"。

## 一、基本概念：四件事串成一句话

> **数据** → 由**数据元素**组成 → 元素由**数据项**组成 → 元素间有**数据元素关系（结构）**

- **数据项**是最小单位（如学生的"姓名"字段）；**数据元素**是基本单位（一个学生记录）
- **数据对象**：性质相同的数据元素的集合（如"全体学生"）
- **数据结构**：互相之间存在**特定关系**的数据元素的集合 = 元素集 + 关系集 + 运算集

### 逻辑结构 vs 存储结构（408 第一道选择题常客）

**逻辑结构**——数据元素间的关系，与存储无关：

```
集合（无序无重复）
线性结构：一对一（线性表、栈、队列、串）
树形结构：一对多（二叉树、B 树）
图形结构：多对多（有向图、无向图）
```

**存储结构**（物理结构）——逻辑结构在内存里的落法：

| 存储结构 | 思想 | 适用 |
|---|---|---|
| 顺序存储 | 一段连续内存，靠**位置**表相邻 | 查多改少 |
| 链式存储 | 结点 + 指针，靠**指针**表相邻 | 增删多 |
| 索引存储 | 附加索引表（关键字 → 地址） | 数据库、字典 |
| 散列存储 | 哈希函数直接算地址 | 等值查找 |

⚠️ 核心认知：**同一个逻辑结构可以用不同存储结构实现**（线性表既能顺序也能链式）；运算的定义在**逻辑结构**上，运算的实现依赖**存储结构**。

## 二、算法五特性与好算法目标

算法五特性（背）：**有穷性、确定性、可行性、输入（≥0 个）、输出（≥1 个）**。

⚠️ "有穷"是算法和程序的区分点：程序（如操作系统）可以不终止，算法必须有限步结束。

好算法四目标：正确性、可读性、健壮性、**高效性**（时间 + 空间）——高效性就是复杂度分析要量化的东西。

## 三、时间复杂度：数"基本操作的次数"

### 从语句频度到大 O

三步走：

1. 找出**基本操作**（最深嵌套里的那条语句）
2. 数它的执行次数 f(n)（问题规模 n 的函数）
3. 取最高阶项、扔系数 → **大 O**

```c
int sum = 0;
for (int i = 1; i <= n; i++)      // n 次
    for (int j = 1; j <= n; j++)  // n 次
        sum++;                     // 基本操作 → f(n) = n² → O(n²)
```

### 常见复杂度阶梯（从小到大）

$$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$

💡 感性记法：n=10⁶ 时——O(n) 百万次（毫秒级）；O(n log n) 约两千万次（几十毫秒）；O(n²) 万亿次（小时级）。**排序为什么折腾 O(n log n)**，看这张表就懂。

### 大 O 推导规则（408 选择题考点）

1. 加法规则：$T_1 + T_2 = O(\max(f_1, f_2))$——只留最大项
2. 乘法规则：$T_1 \times T_2 = O(f_1 \times f_2)$——嵌套循环相乘
3. 常数和低阶全扔：O(3n² + 100n + 5) = O(n²)

### 典型例子（能手推才算会）

| 代码片段 | 复杂度 | 解释 |
|---|---|---|
| `while (i <= n) i *= 2;` | O(log n) | 每轮翻倍，走 log₂n 轮 |
| `while (n > 1) n /= 2;` | O(log n) | 同上，折半家族 |
| 外层 i 从 1 到 n 乘 2，内层 O(n) | O(n log n) | 归并/堆排的骨架 |
| 递归 `f(n) = f(n-1) + f(n-2)` 裸写 | O(2ⁿ) | 调用树节点数指数爆炸（记忆化后 O(n)） |

### 三种情况复杂度

- **最好/最坏/平均**：如顺序查找分别是 O(1)/O(n)/O(n/2)=O(n)
- 408 题面说"平均时间复杂度"时要乘概率权重（如成功查找 ASL）
- **均摊（摊还）分析**：偶尔很贵、总体便宜——如动态数组扩容，单次 O(n) 但均摊 O(1)

## 四、空间复杂度：额外开了多少

S(n) = 算法**额外**占用的辅助空间随 n 的增长。

| 场景 | 空间复杂度 |
|---|---|
| 原地快排（递归栈深 log n） | O(log n) |
| 归并排序的辅助数组 | O(n) |
| 图的邻接矩阵 | O(n²) |
| 迭代两变量求斐波那契 | O(1) |

⚠️ 空间复杂度**不含**输入数据本身；递归的**栈深**算在内——"递归版快排空间 O(log n)"指的是栈。

## 五、时间换空间、空间换时间

- **空间换时间**：哈希表（O(n) 空间换 O(1) 查找）、记忆化递归、前缀和——**后端工程默认取向**
- **时间换空间**：流式处理、原地排序、位图压缩——内存受限场景（嵌入式、外部排序）
- 没有免费午餐：O(1) 查找的哈希表，最坏仍可能 O(n)（全冲突），所以工程上还要看**期望性能**

## 六、盲点自测

1. 逻辑结构和存储结构谁与"计算机"有关？（存储结构；逻辑结构是数学关系）
2. 栈和队列属于什么逻辑结构？（线性——一对一）
3. `for (i=1; i<=n; i*=2) sum++;` 复杂度？（O(log n)）
4. 大 O 的加法/乘法规则各是什么？（取 max / 相乘）
5. 算法与程序的根本区别？（有穷性）
6. 递归算法的空间复杂度看什么？（递归深度——栈帧）
7. 均摊 O(1) 是什么意思？（最坏偶尔 O(n)，摊到每次操作平均 O(1)）

## 七、动手玩

```python
# 亲眼看看 O(n) vs O(n log n) vs O(n²) 的差距
import time, random

def timeit(fn, arr):
    t = time.perf_counter()
    fn(arr)
    return time.perf_counter() - t

arr = [random.random() for _ in range(100000)]
print('sorted (Timsort, O(n log n)):', timeit(lambda a: sorted(a), arr))

arr2 = arr[:5000]
def bubble(a):               # O(n²)
    for i in range(len(a)):
        for j in range(len(a)-i-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
print('bubble O(n²) on 5000 elements:', timeit(bubble, arr2))
# 十倍的数据，平方复杂度是一百倍的时间——亲手感受
```

## 参考资料

- 王道《数据结构考研复习指导》第 1 章
- 《算法图解》——复杂度的漫画版入门
- [[00-刷题理模型|刷题理模型]]——复杂度分析在实战题里的用法

⬅️ [[00-数据结构总览|总览]] 🏠 [[00-基础与理论|00-基础与理论]] ➡️ [[02-线性表|线性表]]