05. 算法基础¶
算法效率、查找、排序与算法设计策略。
配套阅读：算法基础：课件笔记，含课程配图、例题和参考解析。
配套阅读：【软件设计】数据结构及算法应用：课件笔记，含课程配图、例题和参考解析。
本章目录¶
复杂度、查找、排序与算法策略¶
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 算法效率与查找
## 复杂度的含义
- 时间复杂度：基本操作次数随输入规模 n 增长的趋势，区别于某次运行的实际耗时
- 空间复杂度：所需存储量随输入规模增长的趋势
- 辅助空间只计算输入以外的额外空间，通常包含递归调用栈
- O 表示渐近上界，Θ 表示渐近紧确界，Ω 表示渐近下界
- 最好、平均、最坏情形须区分；平均分析依赖输入分布
- 摊还分析：把一系列操作的总代价分摊到单次操作，不等于随机输入的平均
- 常见增长级别：常数、对数、线性、线性对数、平方、指数、阶乘
## 顺序查找
- 逐一比较关键字，找到目标或遍历结束
- 不要求数据有序，适用于顺序表与链表
- 最好 O(1)，最坏 O(n)
- 等概率成功查找且从头扫描时，平均比较次数为 (n + 1) / 2
## 二分查找
- 前提：按相同比较规则有序；数组等支持随机访问的结构适合高效实现
- 闭区间 [low, high] 中取 `mid = low + (high - low) // 2`
- 比较目标与 `a[mid]`，按结果舍弃不可能包含目标的一半区间
- 找到返回；区间变空则失败；查找首个或末个相等元素需相应调整边界
- 数组实现最坏 O(log n)，迭代实现辅助空间 O(1)
- 链表定位中点需要遍历，不能仅凭比较次数认定总耗时为 O(log n)
## 哈希查找
- 哈希函数把关键字映射到桶或槽位；不同关键字可能发生冲突
- 开放定址：在表内按探测序列寻找位置
- 线性探测是其中一种；删除常需墓碑标记以保留探测链
- 链地址法：同一桶内保存冲突元素的集合或链表
- 装载因子 α = 元素数 / 桶数；装载过高通常增加冲突
- 在哈希分布良好、装载受控等条件下，查找期望 O(1)；最坏可达 O(n)
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 排序：基本概念与简单排序
## 基本概念
- 稳定性：相等关键字记录的相对次序在排序后保持不变
- 原地排序：通常只需常数级辅助空间；递归栈是否计入须明确
- 时间复杂度与输入顺序、实现和数据分布有关
- 以下分析采用常见数组实现；n 为记录数，空间指辅助空间
## 直接插入排序
- 维护有序前缀，把下一个记录插入合适位置
- 大于待插入关键字的记录向后移动，相等记录不跨越即可保持稳定
- 最好 O(n)，平均与最坏 O(n²)，空间 O(1)
- 对短序列或基本有序的序列开销较小
## 希尔排序
- 按步长分组，对各组执行插入排序
- 逐步缩小步长，最后一次步长为 1
- 通常不稳定，空间 O(1)
- 时间复杂度依赖步长序列，不能统一写成 O(n^1.3)
- 使用逐次折半的原始步长序列时，最坏时间可达 O(n²)
## 简单选择排序
- 从未排序区间选出最小值，与区间首元素交换
- 各种输入下比较次数均为 n(n - 1) / 2，时间 Θ(n²)
- 交换次数 O(n)，空间 O(1)，通常不稳定
## 冒泡排序
- 逐对比较相邻元素，逆序时交换，每轮确定一个端点元素
- 相等元素不交换时稳定，空间 O(1)
- 平均与最坏 O(n²)
- 若一轮无交换就提前结束，最好 O(n)
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 排序：堆、分治与基数
## 堆排序
- 堆是满足堆序关系的完全二叉树，可用数组保存
- 升序排序常用大顶堆，堆顶为当前最大值
- 自底向上建堆 O(n)，交换堆顶与末尾后只调整剩余堆
- 共进行 O(n) 次取顶与调整，最坏时间 O(n log n)
- 常见原地、迭代下沉实现辅助空间 O(1)，不稳定
## 快速排序
- 选基准并划分，使较小和较大元素进入相应区间
- 递归处理子区间；大量重复键可采用三路划分
- 划分较均衡或随机基准的期望时间 O(n log n)
- 极度不均衡时最坏 O(n²)，通常不稳定
- 普通递归实现：期望栈空间 O(log n)，最坏 O(n)
- 只递归较小区间、循环处理较大区间，可把栈空间限制为 O(log n)
## 二路归并排序
- 划分序列，分别排序，再合并两个有序子序列
- 合并时相等关键字优先取左侧，可保持稳定
- 常规实现各类输入的时间均为 Θ(n log n)
- 数组归并通常需要 O(n) 辅助空间；递归深度 O(log n)
## 基数排序
- 依据关键字的各位，反复分配与收集
- LSD 从最低位开始，每一轮必须稳定，才能保留前几轮的次序
- n 为记录数，d 为位数，r 为每位的基数
- 每轮采用计数分配的常见数组实现：时间 O(d(n + r))，辅助空间 O(n + r)
- 适用于能拆成有限位且每位取值范围明确的关键字
- 不属于纯比较排序，其复杂度依赖 d 和 r
## 常见实现的稳定性归类
- 稳定：直接插入、冒泡、归并、采用稳定分配的 LSD 基数排序
- 通常不稳定：简单选择、希尔、堆、原地快速排序
- 稳定性取决于实现；不能仅凭时间复杂度判断
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 算法设计策略
## 分治
- 分解：把问题拆成规模更小的同类子问题
- 求解：递归处理子问题，足够小时直接求解
- 合并：把子问题结果组合成原问题结果
- 典型算法：归并排序、快速排序
- 二分查找只保留一个子问题，也常归入减治
## 贪心
- 每一步按既定规则作出当前最优选择，通常不回退
- 获得全局最优需要贪心选择性质与最优子结构等依据
- 典型算法：哈夫曼编码、最小生成树、满足条件的最短路径算法
- 分数背包：物品可分割时，按单位重量价值选择可得到最优解
- 0/1 背包不能普遍使用同一贪心规则
- 找零、装箱、多机调度中的贪心策略可能只是启发式，是否最优取决于具体问题
## 动态规划
- 把原问题转化为状态之间的依赖，保存并复用子问题结果
- 常见条件：最优子结构与重叠子问题
- 核心：状态定义、状态转移、初始条件、计算顺序与答案位置
- 实现：自顶向下记忆化，或自底向上递推
- 时间通常按状态数与每个状态的转移代价分析
- 典型问题：矩阵链乘法的最优括号化、0/1 背包、最长公共子序列 LCS
## 回溯
- 在解空间中深度优先尝试，遇到不满足约束的选择就回退
- 选择、递归探索、撤销选择，保证分支之间状态正确
- 用约束剪枝跳过不可能产生有效解的分支
- 可求任意一解、所有解或配合界限搜索最优解
- 典型问题：N 皇后、迷宫、排列组合、背包搜索
- 最坏复杂度常为指数级，剪枝效果依赖问题与输入