第1章 绪论
本章介绍数据结构的基本概念、算法复杂度分析方法。掌握时间复杂度的计算方法是考研的必备基础。
1. 数据结构基本概念
数据结构三要素
数据结构是一个二元组 D = (D, S)，其中 D 是数据元素的有限集合，S 是 D 上关系的有限集合。数据结构包含三个要素：
| 要素 | 说明 | 例子 |
|---|---|---|
| 逻辑结构 | 元素之间的逻辑关系，独立于计算机存储 | 线性结构、树形结构、图形结构 |
| 存储结构 | 数据在计算机中的存储方式 | 顺序存储、链式存储 |
| 数据运算 | 对数据元素的操作 | 插入、删除、查找、遍历 |
逻辑结构分类
线性结构：元素之间一对一关系
- 线性表、栈、队列、串
非线性结构：
- 树形结构：元素之间一对多关系（树、二叉树）
- 图形结构：元素之间多对多关系（有向图、无向图）
- 集合结构：元素之间除"同属一个集合"外无其他关系
存储结构分类
顺序存储：用连续地址存储，逻辑相邻=物理相邻
- 优点：随机存取O(1)、空间利用率高
- 缺点：插入删除需移动元素、需预先分配连续空间
链式存储：用指针表示逻辑关系
- 优点：插入删除O(1)、动态分配空间
- 缺点：不能随机存取、指针占用额外空间
2. 时间复杂度
大O记号定义
若存在正常数 c 和 n₀，使得当 n ≥ n₀ 时，有 0 ≤ T(n) ≤ c·f(n)，则称 T(n) = O(f(n))。
大O记号表示算法时间复杂度的上界。
常见复杂度排序
O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
时间复杂度计算方法
累加法（循环嵌套）
python
def example1(n):
count = 0
for i in range(n): # 执行 n 次
for j in range(n): # 执行 n 次
count += 1 # O(1)
# 总次数 = n × n = n²
# 时间复杂度 = O(n²)
return count计算思路：循环嵌套的次数相乘
乘法法则（循环内外）
python
def example2(n):
for i in range(n): # On)
pass
for j in range(n*n): # O(n²)
pass
# 总复杂度 = O(n) + O(n²) = O(n²)计算思路：并列取最大值
递归法（递推方程）
示例1：阶乘递归
python
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)递推式：T(n) = T(n-1) + O(1) 展开：T(n) = T(n-2) + O(1) + O(1) = ... = O(n)
示例2：斐波那契
python
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)递推式：T(n) = T(n-1) + T(n-2) + O(1) = O(2ⁿ)
示例3：二分查找
递推式：T(n) = T(n/2) + O(1) 展开：T(n) = T(n/4) + O(1) + O(1) = O(log₂n)
手写计算示例
计算以下代码的时间复杂度：
python
def mystery(n):
for i in range(1, n+1): # i = 1, 2, 3, ..., n
for j in range(i): # j = 0, 1, ..., i-1
print(i, j)分析过程：
i=1 时：j 循环 1 次
i=2 时：j 循环 2 次
...
i=n 时：j 循环 n 次
总次数 = 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²)3. 空间复杂度
定义
算法所需额外存储空间的规模，记为 S(n) = O(g(n))。
原地算法
如果算法所需辅助空间为常数，即 O(1)，则称该算法为原地算法。
示例：冒泡排序
python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# 只用了常数个临时变量 (i, j, n)
# 空间复杂度 = O(1)，原地算法对比：归并排序
python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 需要额外空间
right = merge_sort(arr[mid:]) # 需要额外空间
return merge(left, right)
# 空间复杂度 = O(n)，非原地算法4. 考研重点 & 易错点
高频考点
| 考点 | 要点 |
|---|---|
| 时间复杂度计算 | 递推式求解、循环嵌套分析 |
| 大O记号 | 只保留最高次项，系数为1 |
| 常见算法复杂度 | 二分查找O(logn)、快速排序O(nlogn)等 |
| 数据结构三要素 | 逻辑结构、存储结构、数据运算 |
易错点
| 易错点 | 正确理解 |
|---|---|
| 混淆平均、最坏、最好复杂度 | 考研默认指最坏时间复杂度 |
| 递归算法复杂度计算 | 必须写出递推式再求解 |
| 空间复杂度忽略输入空间 | 只计算算法使用的额外空间 |
log₂n 底数省略 | 在大O记号中底数不重要 |
常用计算技巧
等比数列求和：1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1
调和级数：1 + 1/2 + 1/3 + ... + 1/n ≈ ln n
5. 算法效率对比表
| 操作/算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| 顺序查找 | O(n) | 无序、小规模 |
| 二分查找 | O(logn) | 有序顺序表 |
| 冒泡/插入排序 | O(n²) | 小规模、基本有序 |
| 快速/归并/堆排序 | O(nlogn) | 大规模 |
| 斐波那契递归 | O(2ⁿ) | ❌ 应改用动态规划 |
| 矩阵乘法 | O(n³) | 可用优化算法 |
📝 代码示例：复杂度分析工具
python
def analyze_complexity():
"""
示例代码，展示不同复杂度
"""
n = 100
# O(1) 常数时间
x = n + 1
# O(logn) 对数时间
i = 1
while i < n:
i *= 2
# O(n) 线性时间
for i in range(n):
pass
# O(nlogn) 线性对数时间
for i in range(n):
j = 1
while j < n:
j *= 2
# O(n²) 平方时间
for i in range(n):
for j in range(n):
pass
if __name__ == "__main__":
analyze_complexity()
print("复杂度分析示例执行完成")