动机
程序在几个例子上给出合理答案,是证据,却未证明对所有合法输入都正确。短程序也未必快。算法分析分开两个问题:结果是否满足规格,以及输入增大时需要多少工作。有效的证明须说明输入假设、执行过程保持什么性质,以及执行为何终止。
数组从零编号。除非另述,假设随机存取机模型中,索引运算与元素比较均为常数时间。后面的复杂度断言依赖这些假设。
定义
定义 1.1.1
(规格与正确性)
前置条件描述合法输入及初始状态假设;后置条件描述所需结果。算法若在每次由前置条件开始且终止的执行中,都满足后置条件,称为部分正确。若还保证每次这种执行均终止,则为完全正确。循环不变量是在第一次迭代前成立,且每次实际执行的迭代都保持的命题。
使用不变量时,先证初始化及保持性,再把它与循环条件的否定结合,推出后置条件。不变量不必就是后置条件,因为它须描述工作尚未完成的中间状态。证明终止可用每次迭代严格减少的非负整数,称为变式(variant)。只说某变量有改变不足够,它可能无限增大或来回摆动。
定义 1.1.2
(渐近界与输入大小约定)
对最终非负的函数, 表示存在与 无关的常数 ,使所有 都满足 。反向的常数倍下界记作 ,两者均成立记作 。最坏时间是所有大小为 的合法输入中,成本的最大值;最佳或平均时间是不同断言,须另行定义。
必须先指定输入大小。含 个固定大小键值的列表,其大小与 成正比;正整数 的二进制表示却只需 比特。执行 次迭代虽然对数值为线性,未必对比特长度为多项式时间。任意长整数的加法也不能自动视作单位成本。计算模型是定理的一部分,不能在结论之后才补猜。
定理 / 命题
定理 1.1.3
(半开区间的二分搜索)
设 按非递减次序排列,目标为 。以下算法在目标存在时返回含 的索引,否则返回 NOT_FOUND。它在 次迭代内终止,使用常数辅助空间。
lo = 0; hi = n
while lo < hi:
mid = lo + floor((hi - lo) / 2)
if A[mid] < t:
lo = mid + 1
else if A[mid] > t:
hi = mid
else:
return mid
return NOT_FOUND
定理 1.1.4
(合并排序)
递归地排序两半,再合并已排序的两半,所得结果是输入的已排序排列。若合并以线性次数读写元素,则 时最坏时间为 。标准数组实现除输入外使用 辅助存储,另有 递归栈。
证明思路或证明
证明
(二分搜索:不变量与终止)
二分搜索保持 ,以及“若目标在任何地方出现,则它在半开区间 的某索引出现”。最初整个数组均保留。若 ,有序性排除所有不大于 的索引,更新 后命题仍真。若 ,有序性排除所有不小于 的索引,更新 后仍真。相等时立即返回合法索引。若正常离开循环,区间已空,不变量遂保证目标从未出现。
整数长度 在每次没有返回的迭代中严格下降,且保持非负。循环执行时 ,每次更新至少移去中点或包含中点的一段;新长度至多为旧长度一半的下整数。因此 时至多有 次迭代, 时没有迭代。中点公式也避免直接计算 ;固定宽度整数仍须能安全表示容许的索引差。若有重复值,此算法未保证返回第一次出现的位置,那是另一规格。
证明透视
正确性与终止填补不同缺口
二分搜索不变量指出存在的目标必须留在哪里,本身却不保证循环停止。递减区间长度补上此论证。反之,区间缩小只能证明终止,不能证明丢弃位置安全。必须逐一检查每个分支的保持性与严格下降,两者合起来才完成证明。
证明合并运算
证明
(合并得到有序排列)
设两个输入序列 已排序。维持指向各自第一个未使用元素的指针,以及输出前缀。不变量说明:此前缀已排序,恰好包含已消耗的元素及其重数,而且每个已输出元素均不大于任何未使用元素。开始时前缀为空。选较小的当前首元素,相等时取左边,并附加到输出。各首元素均为自身剩余部分的最小值,所以选出的元素在全部剩余元素中最小,保持不变量。当某序列耗尽,把另一序列已排序、且不小于输出前缀的剩余部分接上。
每次输出一个元素,未使用元素数便减一,故必终止。最后结果已排序且完整保留全部输入元素及重数。单证有序性不足够:丢弃全部键值也会输出有序序列。相等时先取左边,还保持两半中相等键的相对次序;若递归排序亦稳定,整个算法便稳定。
递归正确性与时间式
证明
(合并排序:归纳与递推式)
对 作强归纳。空数组及单元素数组已是自身的有序排列。若 ,两半均较小,归纳假设保证它们的排序结果正确;合并证明再保证合并结果是原输入的有序排列。这是循环不变量证明的递归对应;递归调用须有更小参数及基本情形,不能自行证明自己。
当 为二的幂,时间满足 的常数倍界,基本成本为常数。第 层有 个大小 的子问题,非递归总工作与 成正比。共有 个非叶层,叶节点只加线性工作,故得到所述阶。一般 使用上下整数两半,树深至多 ,每层合并总工作至多线性,得上界。对下界,前 层中,每层的子数组长度均至少为二、总长度为 ,合并它们至少付出线性的复制成本,所以总和为 。这是对指定合并实现的下界,不是所有排序算法的下界。
空间、递推式与计数对象
时间式加上两个递归调用的成本,因为两者均执行。最高同时使用的辅助空间却不同:两调用可依次进行,共用一个临时数组。长度 的缓冲区已足够,同时存在的调用记录只有对数个。把整次执行分配过的空间相加,是总分配量而非最高存活内存;两者未必相同。
写递推式前必须解释各项。分成两半不自动产生对数时间:二分搜索只走一支,合并排序却走两支。 虽每次处理较小输入,累加等差数列却得二次增长。每次合并额外作一次线性复制只改变常数;若合并本身为二次,便改变渐近阶。应由算法决定递推式,不能反过来凭想要的答案挑选递推式。
概念视角分析
精确解出的递推式
合并长度为 和 的两个序列至多需要 次比较,所以当 时,最坏比较次数满足 ,。共 层,每层贡献 减去该层的合并次数,而合并总共有 次,故
当 时为 ,与对全部 个输入的穷举检查一致。因此 的阶可以写成带有明确线性修正项的精确公式。
例题详解
例题 1.1.5
(搜索失败也有正确性证明)
在 搜索五。初始 的中点二含四,更新为 。中点四含九,得 ;中点三含八,得 ,返回失败。不变量在每步排除被移去的位置,所以失败是正确结果,并非例外状态。
例题 1.1.6
(插入排序与不同时间界)
插入排序在第 次迭代开始时,保持长度 的前缀是原前缀的有序排列。把下一键插入并右移较大键,可保持此性质,最后排序全数组。递增输入每次插入只需一次失败比较,标准实现为线性。递减输入须移动 个键,最坏为二次。说插入排序是二次,描述的是最坏情况,而非每个输入。
例题 1.1.7
(数值与二进制长度)
考虑从零数到正整数输入 的循环。若 ,输入有 比特,循环却执行 次,对比特长度为指数。称它线性,只有以数值 为参数才有意义,并未建立二进制整数上的多项式时间算法。若计数器的长度亦增长,比特运算计数还可能增加成本。
常见错误
反例模式
在未排序数组上作二分搜索
一个诱人的说法是:只要目标在数组中出现,循环就能找到它。取 、。起初 、,中点 ,,故 。接着 ,,故 ,循环结束并返回 NOT_FOUND,然而 。失效的不变量步骤是对有序性的使用:“ 排除所有不小于 的索引”只有在 非递减时才成立,这里它错误地丢弃了索引 。修正办法就是前置条件本身:搜索开始前,数组必须按非递减次序排列。
常见错误
(只证明成功的分支)
不变量必须涵盖每个合法分支,包括相等与空输入。只测成功搜索,没有证明失败规格。终止证明应用有下界的量,不能只说搜索区域改变。
常见错误
(把大 O 当成等式或最坏情况)
大 O 是上界,不是等式,也不是最坏情况的同义词。常数函数也属 ,只是这个界信息不足。不同固定底数的对数只差常数因子,底数影响精确计数,却不改变 分类。平均情况须指定输入分布,不能当作最坏保证。
总结
正确性需要规格、保持性及终止论证。时间需要成本模型、输入大小与有理由的计数。二分搜索缩小一个候选区间;合并排序处理两半并付出组合成本。两者虽同属分治,递推式却反映不同的实际工作。
练习
快速检查
(改为找第一个满足 的索引,若无则返回 。给不变量并解释更新。)
说明 以下及 以上(含)的索引应满足什么。
解答 · 引导解答
保持所有小于 的索引值都小于 ,所有不小于 的索引值都至少为 ,以及 。起始外部区域均空。若 ,设 ,否则设 。有序性证明保持,区间长度如前严格减少。终止时 分隔两区,故为第一个合格索引或 。相等时须走后一分支,保留较早的相等键。
快速检查
(对二的幂及正常数基本成本,解 及 。)
数出递归的层数及每层的成本。
解答 · 答案
写 ,第一式展开 次,得常数加 ,所以 时为 。第二式每个内层成本为 ,共有 层,另有 个常数成本叶节点,故为 。
快速检查
(程序设计者说只检查输出有序便证明排序正确。给反例及缺少的后置条件。)
想想一个必然有序、却毫无用处的算法。
解答 · 答案
对任何输入均返回空数组,输出总有序,却没有保留输入元素。缺少的是输出须为输入的排列,包含重数;只检查长度仍会容许用不相关的相等键替代。
快速检查
(给出 的明确常数,证明 。)
把 与 同 比较。
解答 · 答案
当 ,由 、,有 。下常数三、上常数十四、阈值一,证明所述 界。