程序 = 数据结构 + 算法。用合适的结构组织数据，用高效的算法处理问题。
数据结构和算法是程序员的"内功心法"。面试必考、工作常用，更是写出高性能代码的基础。本章从最基础的数组讲到动态规划，让你对算法世界建立系统认知。
9.1 时间复杂度：Big-O 表示法
在讨论算法之前，我们必须先学会评判算法的"好坏"。时间复杂度描述算法执行时间随输入规模增长的变化趋势。
常见复杂度排序
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)| 复杂度 | 名称 | 典型算法 | n=100 时 |
|---|---|---|---|
| O(1) | 常数 | 数组索引 `arr[5]` | 1 |
| O(log n) | 对数 | 二分查找 | ~7 |
| O(n) | 线性 | 遍历数组 | 100 |
| O(n log n) | 线性对数 | 快速排序 | ~664 |
| O(n²) | 平方 | 冒泡排序 | 10000 |
| O(2ⁿ) | 指数 | 暴力穷举子集 | 天文数字 |
如何分析复杂度
def find_max(arr):
max_val = arr[0] # O(1)
for num in arr: # 循环 n 次
if num > max_val: # O(1)
max_val = num # O(1)
return max_val
# 总复杂度：O(n)
def has_duplicate(arr):
for i in range(len(arr)): # O(n)
for j in range(i + 1, len(arr)): # O(n)
if arr[i] == arr[j]:
return True
return False
# 总复杂度：O(n²)
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right: # 每次循环将范围减半
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 总复杂度：O(log n)分析原则：
- 保留最高阶项，忽略常数和低阶项：
3n² + 2n + 100→O(n²) - 关注最坏情况（除非特别说明平均情况）
9.2 数组与链表
数组（Array）
内存中连续的存储空间，通过索引 O(1) 时间访问任意元素。
内存地址： 1000 1004 1008 1012 1016
┌────┬────┬────┬────┬────┐
数组元素：│ 10 │ 20 │ 30 │ 40 │ 50 │
└────┴────┴────┴────┴────┘
索引： 0 1 2 3 4# Python 的 list 是动态数组
arr = [10, 20, 30, 40, 50]
arr[2] # O(1) — 随机访问
arr.append(60) # O(1)* — 末尾追加（均摊）
arr.insert(0, 5) # O(n) — 插入到开头，所有元素后移
arr.pop(0) # O(n) — 删除开头元素*Python 的 list 是动态数组：当容量不足时自动扩容（通常是 1.125~2 倍），append 的均摊时间复杂度为 O(1)。
链表（Linked List）
通过指针连接的节点序列，内存不一定连续。
┌──────────┐ ┌──────────┐ ┌──────────┐
头部 ──> │ data: 10 │──> │ data: 20 │──> │ data: 30 │──> None
│ next ────── │ next ────── │ next │
└──────────┘ └──────────┘ └──────────┘# 链表节点定义
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 创建链表：10 -> 20 -> 30
head = ListNode(10)
head.next = ListNode(20)
head.next.next = ListNode(30)
# 遍历链表
def print_list(head):
current = head
while current:
print(current.val, end=" -> ")
current = current.next
print("None")
print_list(head) # 10 -> 20 -> 30 -> None
# 在头部插入（O(1)）
new_head = ListNode(5)
new_head.next = head
head = new_head
# 在尾部插入（O(n)，因为需要遍历到末尾）
def append(head, val):
if not head:
return ListNode(val)
current = head
while current.next:
current = current.next
current.next = ListNode(val)
return head
# 反转链表（经典面试题！）
def reverse_list(head):
prev = None
current = head
while current:
next_temp = current.next # 暂存下一个
current.next = prev # 反转指针
prev = current # 前移 prev
current = next_temp # 前移 current
return prev数组 vs 链表
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问 | O(1) ✅ | O(n) ❌ |
| 头部插入/删除 | O(n) | O(1) ✅ |
| 尾部插入/删除 | O(1) | O(1)（有尾指针）/ O(n) |
| 内存使用 | 连续（可能浪费） | 不连续（指针开销） |
| 缓存友好 | 是 ✅ | 否 ❌ |
💡 实践建议：绝大多数场景用数组（Python list）即可。链表主要用于实现更高级的数据结构（如 LRU 缓存、图的邻接表）。
9.3 栈与队列
栈（Stack）
后进先出（LIFO）——像一叠盘子，最后放的先取。
入栈 push(3): 出栈 pop():
┌───┐ ┌───┐
│ 3 │ <─ 栈顶 │ │
├───┤ ├───┤
│ 2 │ │ 2 │ <─ 栈顶
├───┤ ├───┤
│ 1 │ │ 1 │
└───┘ └───┘# Python 用 list 模拟栈
stack = []
stack.append("a") # push
stack.append("b")
stack.append("c")
print(stack.pop()) # "c"（后进先出）
print(stack.pop()) # "b"
print(stack[-1]) # "a"（peek：查看栈顶但不弹出）
print(len(stack)) # 1
# 栈的经典应用：括号匹配
def is_valid_parentheses(s):
"""检查括号是否匹配"""
stack = []
pairs = {")": "(", "]": "[", "}": "{"}
for char in s:
if char in "([{":
stack.append(char)
elif char in ")]}":
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0 # 栈空了才说明全部匹配
print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("([)]")) # False队列（Queue）
先进先出（FIFO）——像排队买票，先来的先服务。
入队 enqueue(1): 出队 dequeue():
队尾 队首 队尾 队首
↓ ↓ ↓ ↓
[3, 2, 1] → [3, 2] → [3]from collections import deque
# deque（双端队列）——两端操作都是 O(1)
queue = deque()
queue.append("a") # 入队（右侧）
queue.append("b")
queue.append("c")
print(queue.popleft()) # "a"（左侧出队，FIFO）
print(queue.popleft()) # "b"
queue.appendleft("x") # 左侧入队
print(queue) # deque(['x', 'c'])
# 队列的经典应用：BFS（广度优先搜索，见 9.7 节）9.4 哈希表（Hash Table）
通过哈希函数将键映射到存储位置，实现接近 O(1) 的查找。
# Python 的 dict 和 set 都是基于哈希表
phone_book = {
"张三": "138-0000-0001",
"李四": "138-0000-0002",
}
print(phone_book["张三"]) # O(1)
# set：元素不重复的集合
visited = set()
visited.add("A")
visited.add("B")
visited.add("A") # 重复，被忽略
print(visited) # {'A', 'B'}
print("A" in visited) # True，O(1) 查询哈希冲突与解决
哈希函数：hash(key) % 10
键 "abc" → hash("abc") % 10 = 5 → 存入位置 5
键 "xyz" → hash("xyz") % 10 = 5 → 冲突！
解决方法：
1. 拉链法：位置 5 存一个链表 [("abc", val1), ("xyz", val2)]
2. 开放寻址法：位置 5 被占，尝试 6、7、8...Python 的 dict 使用开放寻址法，通过巧妙的探测序列实现高性能。
实际应用
# 1. 两数之和（LeetCode 经典题）
def two_sum(nums, target):
"""找到两个和为 target 的数的索引"""
seen = {} # {值: 索引}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
# 2. 字符频率统计
from collections import Counter
text = "abracadabra"
freq = Counter(text)
print(freq) # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
print(freq.most_common(2)) # [('a', 5), ('b', 2)]9.5 树与二叉树
基本概念
1 ← 根节点（root）
/ \
2 3 ← 中间节点
/ \ \
4 5 6 ← 叶子节点
节点 2 是节点 4 和 5 的父节点
节点 4 和 5 是兄弟节点
树的高度（深度）：3二叉树的遍历
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 创建树：
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 前序遍历：根 → 左 → 右
def preorder(node):
if not node:
return
print(node.val, end=" ") # 先访问根
preorder(node.left)
preorder(node.right)
# 中序遍历：左 → 根 → 右 （BST 排序输出）
def inorder(node):
if not node:
return
inorder(node.left)
print(node.val, end=" ") # 中间访问根
inorder(node.right)
# 后序遍历：左 → 右 → 根 （先处理子树）
def postorder(node):
if not node:
return
postorder(node.left)
postorder(node.right)
print(node.val, end=" ") # 最后访问根
# 层序遍历（BFS）
from collections import deque
def level_order(root):
if not root:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
preorder(root) # 1 2 4 5 3
inorder(root) # 4 2 5 1 3
postorder(root) # 4 5 2 3 1
level_order(root) # 1 2 3 4 5二叉搜索树（BST）
左子树所有节点 < 根节点 < 右子树所有节点，查找/插入/删除平均 O(log n)。
8
/ \
3 10
/ \ \
1 6 14
/ \
4 7def search_bst(root, target):
"""在 BST 中查找目标值"""
if not root or root.val == target:
return root
if target < root.val:
return search_bst(root.left, target)
return search_bst(root.right, target)9.6 排序算法
冒泡排序 — O(n²)
最简单的排序，像气泡一样将最大值"浮"到末尾。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
# 每一轮将最大的元素"冒泡"到最后
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 优化：本轮无交换，说明已有序
break
return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]快速排序 — O(n log n) 平均
分治法的核心：选一个基准（pivot），小的放左边，大的放右边，递归处理。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # 选择中间元素为基准
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
# [1, 1, 2, 3, 6, 8, 10]
# 原地快排版本（节省内存，面试常考！）
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort_inplace(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pi = partition(arr, low, high)
quick_sort_inplace(arr, low, pi - 1)
quick_sort_inplace(arr, pi + 1, high)
return arr归并排序 — O(n log n) 稳定
分治 + 合并：先递归拆分，再两两合并有序子数组。
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)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 追加剩余元素
result.extend(left[i:])
result.extend(right[j:])
return result排序算法对比
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| Python sort | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
💡 Python 的内置 `sorted()` 和 `list.sort()` 使用 Timsort（归并+插入排序的混合算法），在绝大多数场景下是最优选择。
9.7 搜索算法
二分查找 — O(log n)
前提：数组必须有序。
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # 防止溢出
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7)) # 3
print(binary_search(arr, 6)) # -1（未找到）深度优先搜索 DFS
像走迷宫：沿一条路走到底，无路可走再回头。
# 图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
def dfs_iterative(graph, start):
"""DFS 迭代版本（使用栈）"""
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
print(node, end=" ")
visited.add(node)
# 将邻居加入栈（可以反转以控制顺序）
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
def dfs_recursive(graph, node, visited=None):
"""DFS 递归版本（更简洁）"""
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
print("迭代 DFS：", end="")
dfs_iterative(graph, 'A') # A C F E B D
print("\n递归 DFS：", end="")
dfs_recursive(graph, 'A') # A B D E F C广度优先搜索 BFS
像水波扩散：一层一层往外探索。天然适合找最短路径。
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print("BFS：", end="")
bfs(graph, 'A') # A B C D E FDFS vs BFS
| 特性 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归/显式栈） | 队列 |
| 空间复杂度 | O(h) h=深度 | O(w) w=宽度 |
| 最短路径 | 不一定 | 保证 ✅ |
| 适用场景 | 迷宫、回溯、拓扑排序 | 最短路径、层序遍历 |
9.8 动态规划入门
动态规划（DP）将复杂问题分解为子问题，记忆已解决的结果避免重复计算。
斐波那契数列：从递归到 DP
# 版本1：朴素递归 — O(2ⁿ) 指数级，大量重复计算
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# fib_naive(50) → 等到天荒地老...
# 版本2：记忆化递归 — O(n)，自上而下
def fib_memo(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
# fib_memo(50) → 瞬间完成
# 版本3：动态规划 — O(n)，自下而上
def fib_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 版本4：空间优化 DP — O(n) 时间，O(1) 空间
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
print(fib_optimized(50)) # 12586269025经典问题：0/1 背包
def knapsack(weights, values, capacity):
"""
0/1 背包问题
weights: 物品重量列表
values: 物品价值列表
capacity: 背包容量
返回：最大价值
"""
n = len(weights)
# dp[i][w]：考虑前 i 个物品，容量 w 时的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] <= w:
# 选或不选当前物品，取最大值
dp[i][w] = max(
dp[i - 1][w], # 不选
dp[i - 1][w - weights[i - 1]] + values[i - 1] # 选
)
else:
dp[i][w] = dp[i - 1][w] # 装不下，只能不选
return dp[n][capacity]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(f"最大价值: {knapsack(weights, values, capacity)}") # 10
# 选择物品1(2,3) + 物品4(5,6) = 重量7, 价值9
# 或 物品2(3,4) + 物品3(4,5) = 重量7, 价值9
# 或 物品2(3,4) + 物品4(5,6) = 重量8, 价值10 ← 最优9.9 图的基本概念
A ──── B
│ │ \
│ │ E
│ │ /
C ──── D
顶点（Vertex）：A, B, C, D, E
边（Edge）：A-B, A-C, B-D, B-E, C-D, D-E
度（Degree）：A 的度为 2（连接 B 和 C）
路径：A → C → D → E（长度为 3，经过 4 个顶点）图的分类：
- 有向图 vs 无向图：边是否有方向
- 加权图：边上有权重（如距离、代价）
- 连通图：任意两个顶点之间都有路径
# 图的三种常用表示法
V = ['A', 'B', 'C', 'D', 'E']
# 1. 邻接矩阵（适合稠密图）
matrix = [
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 1],
[1, 0, 0, 1, 0],
[0, 1, 1, 0, 1],
[0, 1, 0, 1, 0],
]
# 2. 邻接表（适合稀疏图，最常用）
adj_list = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'D'],
'D': ['B', 'C', 'E'],
'E': ['B', 'D'],
}
# 3. 边列表（适合只需要遍历所有边的场景）
edges = [
('A', 'B'), ('A', 'C'),
('B', 'D'), ('B', 'E'),
('C', 'D'), ('D', 'E'),
]9.10 算法学习路线建议
入门 → 基础 → 进阶 → 高级
排序 栈/队列 贪心算法 高级图算法
二分查找 哈希表 分治法 线段树/树状数组
递归 BFS/DFS 动态规划 并查集
二叉树 回溯法 KMP/字符串算法刷题平台推荐： LeetCode、牛客网、Codeforces
刷题策略：
- 按"标签"刷，每类 10-20 题，建立直觉
- 先思考 10-15 分钟，不会再看题解
- 理解题解后，合上自己写一遍
- 定期复习，总结模板
本章小结
- Big-O 是评判算法的核心工具，关注最坏情况和数据规模
- 数组 O(1) 随机访问，链表 O(1) 头部操作
- 栈（LIFO）用于括号匹配、DFS；队列（FIFO）用于 BFS
- 哈希表提供 O(1) 查找，是日常编程中最常用的结构
- 树的三种 DFS 遍历 + BFS 层序遍历，是面试高频考点
- 快排和归并排序是最重要的排序算法，理解其分治思想
- 动态规划的核心：状态定义 + 状态转移方程 + 记忆化
[⬅️ 上一章：08-编程入门-Python](./08-编程入门-Python.html) · [🏠 目录](./README.html) · [➡️ 下一章：10-数据库基础](./10-数据库基础.html)