数据结构与算法 / 系统课时
输入规模与基本操作
输入规模与基本操作
复杂度分析的第一步不是立即写出大 O,而是先回答两个问题:输入有多大,以及算法主要重复了什么工作。本课将建立输入规模和基本操作的选择方法,并通过线性查找得到可核验的操作计数。
学习目标
- 根据问题类型选择能够反映工作量的输入规模。
- 识别算法中的基本操作,并解释选择依据。
- 从代码执行过程得到最好、最坏情况下的操作次数。
为什么要定义输入规模
输入规模是描述问题实例大小的参数,通常记为 n。同一个算法处理不同规模的输入时,执行成本会随 n 变化,因此复杂度分析研究的是成本函数随输入规模增长的趋势。
n 的含义必须由问题决定。数组算法通常使用元素个数;矩阵算法可能使用行数和列数;图算法常同时使用顶点数 |V| 与边数 |E|;整数算法则更适合使用二进制位数,而不是整数本身的数值。
| 问题类型 | 合理的输入规模 | 不宜采用的替代量 |
|---|---|---|
| 数组查找 | 元素个数 n |
数组元素之和 |
| 矩阵乘法 | 稠密矩阵用三项相容维度,稀疏实现还看非零元素的数量与布局 | 单个非零值的数值大小 |
| 图遍历 | 顶点数与边数 | 顶点编号的最大值 |
| 大整数运算 | 二进制位数 | 整数的十进制数值 |
例如,整数 1024 的数值比 16 大很多,但二进制表示只需要 11 位。若算法按位处理整数,位数才与真实工作量直接相关。
如何选择基本操作
基本操作是能够代表算法主要成本、并且便于计数的操作。它不一定是机器执行的单条指令,而是分析模型中选定的单位工作。
选择时应满足三个条件:
- 与核心任务直接相关,例如查找中的关键字比较。若关键字是变长字符串,再说明单次比较的最坏代价,不能把每次比较都当成等长工作。
- 在主要循环中反复发生,其次数会随输入规模显著变化。
- 定义清楚且可稳定计数,不依赖日志、调试输出或偶然的运行环境。
对于同一段代码,选择“比较次数”或“循环次数”可能得到不同的精确函数,但只要二者相差常数倍,通常会得到相同的渐进结论。分析时应先说明计数对象,避免把不同口径的结果混在一起。
从线性查找得到计数函数
在线性查找中,输入规模是列表长度 n,基本操作可以定义为“当前元素与目标值的一次相等比较”。下面的程序返回目标下标,并同步统计比较次数。
def linear_search(values, target):
for index, value in enumerate(values):
if value == target:
return index, index + 1
return -1, len(values)
values = [4, 7, 2, 9, 5]
for target in (4, 2, 8):
print(target, linear_search(values, target))
print("重复命中:", linear_search([9, 2, 9], 9))
print("空输入:", linear_search([], 9))前三行依次返回 (0, 1)、(2, 3)、(-1, 5)。约定返回首次命中的下标,未命中返回 -1,调用者须先判断才能取下标,因为 Python 的 -1 也能索引最后一项。空表比较次数是 0。非空表最好比较 1 次,最坏比较 n 次(未命中,或第一个目标在末尾)。
若命中概率为 ,且命中时首个匹配位置在 1 到 n 等可能,则期望比较次数为 。例如 n=5、p=1/2 时为 4 次。该平均依赖查询分布。重复元素多时,首个匹配位置未必均匀。
边界与易混淆点
输入值不等于输入规模
数值更大不一定代表输入更长。对整数做按位运算时,输入规模通常是位数;对数组做遍历时,元素值大小通常不影响循环次数。
操作次数不等于实际毫秒数
操作计数用于建立与硬件相对独立的分析模型。真实运行时间还受语言实现、处理器、缓存、编译器和输入分布影响。复杂度分析用于比较增长趋势,基准测试用于测量具体环境中的耗时,两者不能互相替代。
代码行数不等于工作量
一行代码可能只执行一次,也可能位于循环中执行 n 次。分析应跟踪动态执行次数,而不是静态统计源码行数。
本课练习
- 分析在长度为
n的数组中求和的算法。指定一种基本操作,分别给出该操作执行次数与n的关系,并说明空数组时的结果。 - 对一个包含
|V|个顶点、|E|条边的邻接表,说明为什么仅用|V|不能完整描述图遍历的输入规模,并给出验收标准明确的计数口径。
本课总结
- 输入规模必须反映问题实例中真正驱动工作量增长的维度。
- 基本操作应与核心任务相关、重复发生且能够稳定计数。
- 精确计数前必须说明分析口径,并区分最好、最坏和依赖概率假设的平均情况。
下一课预告
下一课比较相同求和任务的时间与辅助空间,随后再用渐进记号概括增长。