数据结构与算法 / 系统课时

输入规模与基本操作

输入规模与基本操作

复杂度分析的第一步不是立即写出大 O,而是先回答两个问题:输入有多大,以及算法主要重复了什么工作。本课将建立输入规模和基本操作的选择方法,并通过线性查找得到可核验的操作计数。

学习目标

  • 根据问题类型选择能够反映工作量的输入规模。
  • 识别算法中的基本操作,并解释选择依据。
  • 从代码执行过程得到最好、最坏情况下的操作次数。

为什么要定义输入规模

输入规模是描述问题实例大小的参数,通常记为 n。同一个算法处理不同规模的输入时,执行成本会随 n 变化,因此复杂度分析研究的是成本函数随输入规模增长的趋势。

n 的含义必须由问题决定。数组算法通常使用元素个数;矩阵算法可能使用行数和列数;图算法常同时使用顶点数 |V| 与边数 |E|;整数算法则更适合使用二进制位数,而不是整数本身的数值。

问题类型 合理的输入规模 不宜采用的替代量
数组查找 元素个数 n 数组元素之和
矩阵乘法 稠密矩阵用三项相容维度,稀疏实现还看非零元素的数量与布局 单个非零值的数值大小
图遍历 顶点数与边数 顶点编号的最大值
大整数运算 二进制位数 整数的十进制数值

例如,整数 1024 的数值比 16 大很多,但二进制表示只需要 11 位。若算法按位处理整数,位数才与真实工作量直接相关。

如何选择基本操作

基本操作是能够代表算法主要成本、并且便于计数的操作。它不一定是机器执行的单条指令,而是分析模型中选定的单位工作。

选择时应满足三个条件:

  • 与核心任务直接相关,例如查找中的关键字比较。若关键字是变长字符串,再说明单次比较的最坏代价,不能把每次比较都当成等长工作。
  • 在主要循环中反复发生,其次数会随输入规模显著变化。
  • 定义清楚且可稳定计数,不依赖日志、调试输出或偶然的运行环境。

对于同一段代码,选择“比较次数”或“循环次数”可能得到不同的精确函数,但只要二者相差常数倍,通常会得到相同的渐进结论。分析时应先说明计数对象,避免把不同口径的结果混在一起。

从线性查找得到计数函数

在线性查找中,输入规模是列表长度 n,基本操作可以定义为“当前元素与目标值的一次相等比较”。下面的程序返回目标下标,并同步统计比较次数。

python
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 次(未命中,或第一个目标在末尾)。

若命中概率为 pp,且命中时首个匹配位置在 1 到 n 等可能,则期望比较次数为 p(n+1)/2+(1−p)np(n+1)/2+(1-p)n。例如 n=5、p=1/2 时为 4 次。该平均依赖查询分布。重复元素多时,首个匹配位置未必均匀。

边界与易混淆点

输入值不等于输入规模

数值更大不一定代表输入更长。对整数做按位运算时,输入规模通常是位数;对数组做遍历时,元素值大小通常不影响循环次数。

操作次数不等于实际毫秒数

操作计数用于建立与硬件相对独立的分析模型。真实运行时间还受语言实现、处理器、缓存、编译器和输入分布影响。复杂度分析用于比较增长趋势,基准测试用于测量具体环境中的耗时,两者不能互相替代。

代码行数不等于工作量

一行代码可能只执行一次,也可能位于循环中执行 n 次。分析应跟踪动态执行次数,而不是静态统计源码行数。

本课练习

  1. 分析在长度为 n 的数组中求和的算法。指定一种基本操作,分别给出该操作执行次数与 n 的关系,并说明空数组时的结果。
  2. 对一个包含 |V| 个顶点、|E| 条边的邻接表,说明为什么仅用 |V| 不能完整描述图遍历的输入规模,并给出验收标准明确的计数口径。

本课总结

  • 输入规模必须反映问题实例中真正驱动工作量增长的维度。
  • 基本操作应与核心任务相关、重复发生且能够稳定计数。
  • 精确计数前必须说明分析口径,并区分最好、最坏和依赖概率假设的平均情况。

下一课预告

下一课比较相同求和任务的时间与辅助空间,随后再用渐进记号概括增长。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

输入规模与基本操作

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通