高成本操作可以很少出现
一次二进制递增可能翻转很多位:对末尾有多个一的字加一时,须先把它们归零,再把下一个零设为一。然而由零开始作长序列递增时,每次操作平均翻转位数可以很小。摊还成本限制的是每个允许操作序列的总成本;它不是随机输入上的期望,也不一定限制每一次操作。
固定一个有 位的计数器,由最低有效位 开始编号,存储模 的值。递增会把末尾的一翻成零,再把下一个零翻成一;若原来全为一,则所有 位都翻成零。每次位翻转计一个成本单位,其余成本不计。我们先计算从全零初始状态开始的 次递增;下方的势能证明亦涵盖其他初始状态。循环溢出规则很重要:溢出会执行,而非被拒绝。
定义 1.2.1
(操作集合的摊还上界)
固定一个数据结构、一组允许的操作和一个成本模型。若对每个由指定类别的初始状态出发、含 个允许操作的序列,实际总成本至多为 (其中 只依赖初始状态),则称这些操作的摊还成本至多为 。这一保证针对最坏序列的整体总成本,不涉及概率;个别操作的成本可以远高于 。
总计数
命题 1.2.2
(由零开始的确切翻转总数)
把一个 位模数计数器由零开始,作 次递增,每次位翻转计一个成本单位。总成本恰为
且当 时 。
证明
(逐位计算翻转次数)
从零开始时,包括跨越循环溢出,第 位每 次递增翻转一次;对 ,确切总成本满足
时确切成本为零;严格不等式针对 。为证明逐位计数,第 次递增前,计数器的值为 模 。第 位恰在较低的 位全为一时翻转,亦即 能被 整除时翻转; 也包括在内。数出 中符合者便得到下整项。此上界对 一致成立;单次操作仍可耗费 次翻转。
概念视角代数
翻转次数作为数论量
当 时, 末尾 1 的个数等于 末尾 0 的个数,所以从零开始的第 次递增恰好翻转 个位,其中 是 中素因子 的指数。求和,并利用 ( 为 的二进制展开中 1 的个数),得
这正是 时的势能恒等式:界 的松弛量恰好是 的二进制中 1 的个数。
势能法
定义 1.2.3
(势能与摊还费用)
势能为每个状态 指定一个非负数 。对实际成本为 、使状态由 变为 的操作,其摊还费用定义为
对计数器,取 为值为一的位的个数。
定理 1.2.4
(只含递增时的势能上界)
对 位模数计数器,设初始状态有 个一位,则任意 次递增的总翻转成本至多为 。特别地,由零开始时总成本至多为 。
证明
(每次递增记两个单位,再消去中间项)
若一次递增遇到 个末尾一,则 、 改变 ,故 。若全一后循环溢出,则 、势能改变 ,故 。对任意 次递增求和并消去中间项:
由零开始时 ,总成本最多为 。与上面的确切总计公式不同,此证明也适用任意初始状态,但会多出初始势能的加项。摊还费用是记账工具:势能的负变化可支付翻转,但实际位翻转并没有负成本。
证明透视
势能论证的每个事实用在哪里
证明有两个独立的成分。按末尾一的个数 分情况,是整个证明唯一用到递增规则的地方:每次递增把 个一变成零、把一个零变成一,所以成本是 ,而 改变 ,两者合起来是常数 。循环溢出的情形本质上不同(没有零被设为一),其费用是 而非 。之后把各次费用相加,只有靠 才能收尾:舍去 一项,等式才变成不等式 。
同一个分析也显示论证对其他操作集合在哪里失效。对 作递减,成本为 ,而 由 升至 ,费用为 ,不能以常数为界。这里没有上述的抵消:递减把末尾的零变成一,方向与 所能支付的相反。
四位计数器的八次递增
例题 1.2.5
(四位计数器的八次递增)
由最高有效位开始书写,从 开始。下表只计翻转:
| 递增后次数 | 状态 | 实际翻转 | 一的数目 |
|---|---|---|---|
| 1 | 0001 | 1 | 1 |
| 2 | 0010 | 2 | 1 |
| 3 | 0011 | 1 | 2 |
| 4 | 0100 | 3 | 1 |
| 5 | 0101 | 1 | 2 |
| 6 | 0110 | 2 | 2 |
| 7 | 0111 | 1 | 3 |
| 8 | 1000 | 4 | 1 |
实际总数为 15。此处每次摊还费用都是 2,因此减去最终势能后 。也可计算 。第八次单独成本为四,但操作序列上界仍然成立。
例题 1.2.6
(从非零状态出发)
取 ,由 开始,故 。三次递增依次得到 (翻转 1 次)、(4 次)、(1 次),总成本为 。每次费用都是 ,所以求和等式为 ,因为 有两个一。上界 成立且有余量。由零开始的公式在这里不适用:它会给出 。
例题 1.2.7
(经过循环溢出)
取 ,由 开始,故 。三次递增依次得到 (翻转 1 次,)、(3 次,)、(1 次,)。实际总成本为 ,各次费用之和为 ,而 。这是费用为 而非 的边界情形:全一字是唯一一个递增时不会把任何零设为一的状态。
操作集合为何重要
证明只涵盖递增。模数递减会把末尾零翻成一,再把下一个一翻成零;全零则循环变成全一。
反例模式
允许递减会破坏常数上界
一个自然的说法是:即使也允许递减,每次操作的摊还翻转成本仍为常数。取 及两个 位字符串 与 。对前者递增得到后者,翻转全部 位;对后者递减得到前者,同样翻转全部 位。例如 时这两个字符串是 和 ,每次操作成本为 。因此递增与递减交替作 次操作,成本恰为 。
于是,对这个表示及这个混合操作集合,不存在与 无关的摊还上界,无论用哪种记账方法都一样,因为在这个序列上上界必须超过每次操作 。修补办法是把操作集合限制为只含递增(如上面的定理),或改用另一种表示,并为它另行证明及建立成本模型。
确切公式假设全零初始状态与指定的模数递增。若计数器拒绝溢出、动态增长、计入内存分配或允许其他操作,规格便不同;其成本须按相应规则分析。
常见错误
常见错误
(摊还 O(1) 不等于每次操作 O(1))
因为总成本至多为 就断定每次递增都很便宜,是错的。上表中第八次递增要翻转四位,一般地单次递增可以耗费 次翻转。保证针对的是整个序列的总成本;序列上的平均值低于 ,但个别操作仍可能很贵。
常见错误
(忘记初始势能)
上界 只适用于由零开始。若计数器起初有 个一,正确上界是 。例如由 ()开始,单次递增成本为 ,超过 ;正确上界是 。若只用 、不加初始势能,就会错误地断言这次递增至多花 。
练习
快速检查
(取 ,由 开始递增四次。列出每次翻转成本并核对势能求和等式。)
逐次记下状态及一的数目。
解答 · 答案
各状态为 ,翻转成本依次为 ,总计 。由起点起一的数目为 ,故各次费用为 、、、。等式为 ,成立。
快速检查
(若初始状态为全一,下次模数递增的实际成本及摊还费用是多少?为什么不违反由零开始的总计公式?)
用势能论证中循环溢出的那一种情形。
解答 · 答案
递增后变成全零,实际成本为 。势能由 降至 ,费用为 。这并不矛盾:总计公式假设由零开始;由全一状态出发时,正确上界是 ,而成本 满足此上界。
快速检查
(取 ,写出混合操作例子的两个字符串,以及一对递增—递减中每次操作的翻转成本。)
按 与 的形式写出两个字符串。
解答 · 答案
两个字符串是 与 。对 递增得 ,翻转全部 位;对 递减得 ,同样翻转全部 位。因此一对操作共 次翻转,并回到起点,所以 对(即 次操作)共花 。