本课程之后的每个断言,例如“堆的插入需要对数时间”或“并查集近乎常数”,都是关于代价如何随输入规模增长的陈述。只有说明了计算什么、输入规模是什么、考虑哪些输入,以及符号 、、 的确切含义,这样的陈述才有意义。本单元提供这些基础。它不涉及任何数据结构;之后关于动态数组、堆与排序的单元都依赖它。
代价模型
秒表只能度量某一台机器、某一个编译器和某一个输入。要研究算法本身,我们计算抽象的操作次数。
定义 19.1.1
(单位代价 RAM 模型、输入规模、代价函数)
在单位代价 RAM 模型中,下列每项花费一步:对固定宽度的字作算术运算或比较、读写一个数组单元或变量、一次跳转。输入规模 是指明的参数:数组元素个数、顶点数与边数,或某个数的位数。对算法 与输入 ,令 为步数。最坏情形代价为
最好情形代价取最小值,平均情形代价则在规模为 的输入上按指明的概率分布取期望。
有几种变体值得留意。在比较模型中只计算关键字比较,如排序下界所用的那样。在位代价模型中,对 位的数作算术约花费 步,当数不受字长限制时这很重要。若数不断增大,单位代价假设会产生误导:把一个整数反复平方,每次长度加倍,把每次平方当作一步就低估了工作量。因此,代价断言必定相对于某个模型,输入规模也必须按该模型度量。对以二进制给出的整数 ,输入规模是 位,所以循环执行 次的算法,相对输入规模是指数级的。
记号
定义 19.1.2
(、 与 )
设 。若存在常数 与 ,使得对所有 都有 ,记作 。若存在 与 ,使得对所有 都有 ,记作 。若两者皆成立,即 且 ,记作 。
常数可以依赖 与 ,但不能依赖 。该记号只描述 很大时的行为:阈值 舍弃了有限个小输入。等号只是习惯写法; 代表被 的常数倍从上方界住的函数集合,“”表示 属于该集合。 只给出上界:线性算法同时是 ,这是正确但没有信息量的。 则表示增长阶恰好与 相同。
命题 19.1.3
(增长率的运算规则)
设 。
- 常数与低次项。若 ,系数为实数且 ,则存在 与 ,使对所有 有 ;即 。
- 和。若 且 ,则 。
- 积。若 且 ,则 。
- 传递性。若 且 ,则 。
证明
(吸收低次项与常数相乘)
(1) 若 ,正常数 取 即可;故设 ,并令 。当 时,每个 的 至多为 ,所以 。上界: 时 。下界:。若 ,则 ,故 。取 、、 即可。
(2) 对两个假设分别取 与 。当 时, 。
(3) 对同一范围的 ,所有量都非负,所以两个不等式可以相乘:。
(4) 若 时 ,且 时 ,则 时 。
证明透视
多项式的阈值从何而来
只有 (1) 的下界用到 ;上界只需 。关键一步是把所有低次项归并成单一的 ,使它与首项的比较化为关于 的一个不等式 。阈值 就是首项开始至少占优一倍的位置,而且它依赖系数,并非只依赖 。以 为例:、、,而 恰好在 时成立( 时 )。此处不可能取 之类的阈值,因为 。若 ,则对任何 下界都不成立,因为 最终为负。
对数方面,,所以各底数只差一个常数倍,在 与 中省略底数。
增长层级
当 很大时,常见的阶按下列次序递增:
其中 表示 但 。两个比较可说明证明方法。第一,:由于 时 ,有 。第二,对任何固定的 , 都不是 。令 ,则 ,其极限为 ,所以当 足够大时,每一步至多把 乘以 ,故 。因此 无界。层级中其余比较,我们当作标准事实使用。
命题 19.1.4
( 的极限判别法)
若 且 ,则 。
证明
(夹住比值)
在极限的定义中取 。最终 介于 与 之间,所以对所有足够大的 有 ,这给出 所需的两个界。
概念视角分析
用上极限与下极限刻画记号
当 充分大时若 ,常数可以换成两个极限量: 当且仅当 ; 当且仅当 。对 和 ,比值在 与 之间交替,所以 ,:尽管普通极限不存在,仍然有 。
计算代码的步数
计算最内层语句的执行次数,然后化简。嵌套循环中,若内层次数不依赖外层下标则相乘,否则求和。控制变量每次翻倍的循环约执行 次。
例题
例题 19.1.5
(带明确常数的二次多项式)
证明 。下界:对所有 有 ,所以 、 可用。上界:当 时 且 ,故 ,所以 、 可用。因此 。在 检验:,且 。
例题 19.1.6
(计算循环次数)
考虑 for i in range(n): for j in range(i): work()。循环体在 时执行 次, 时 1 次,一般地 次,总共 次。 时为 10。由于 ,且 时 ,所以次数是 。
再考虑 i = 1; while i < n: i = 2*i。 的取值为 ,一旦 循环便停止。 时,被测试且小于 10 的值为 ,共 4 次迭代 。 时,值 给出 3 次迭代 。一般地,当 时迭代 次;当 时这是 。
例题 19.1.7
(没有极限的 )
设 。 为偶数时 , 为奇数时 ;例如 、。因此对所有 有 ,所以 ,取 、、。比值 在 与 之间交替,没有极限,所以极限判别法不适用,但定义依然适用。极限判别法是充分条件,而不是必要条件。
细节与常见错误
反例模式
指数中的常数
吗?不。,而 无界,所以不存在常数 使 对所有足够大的 成立。相反,。指数中的常数会改变增长类别;乘上常数因子则不会。
常见错误
(把等号当成对称关系)
由 不能写成 ;由 与 也不能推出 。这个等号表示属于: 属于集合 。事实上 是错的,因为 无界。
常见错误
(混淆最坏情形与 O)
“最坏情形”与“”是独立的概念: 界住一个函数,最坏情形则选出是哪一个函数。可以用 描述最好情形代价,也可以用 描述最坏情形代价。
以增长率比较算法时忽略了常数:当 时 大于 ,所以二次算法在小输入上可能更快。渐近分析预测的是缩放行为,例如 翻倍时时间如何变化,而不是某个特定 的运行时间。
习题与解答
快速检查
(1. 证明 是 。)
解答 · 解答 1
当 时 ,所以 。于是对所有 有 。因此 、、 证明 。
快速检查
(2. 计算内层语句执行次数:对 :令 ;当 时令 。求 时的次数,并给出增长类别。)
解答 · 解答 2
对给定的 , 的取值为 ,其中 ,所以循环体执行 次。 时, 的次数为 ,总和为 。一般地,总数至多为 。至少有 个下标满足 ,每个至少贡献 ,所以总数至少为 。两个界都是 阶,所以总数为 。
快速检查
(3. 判断真假并说明理由:(a) ;(b) ;(c) ;(d) ;(e) 。)
解答 · 解答 3
(a) 真:。(b) 假:比值为 ,无界。(c) 真: 时 。(d) 假: 无界。(e) 真:,是 的常数倍。
快速检查
(4. 的算法在 时用 8 ms。预测 时的时间。若改为假设 ,大约又是多少?)
解答 · 解答 4
对 , 变为三倍,时间乘以 ,得 ms。对 ,比值为 。由于 、,比值约为 ,所以约 ms。预测取决于所假设的增长类别,这就是为何必须论证模型。
快速检查
(5. 按增长速度排序:、、、、、。然后求最小的 ,使得对所有 都有 。)
解答 · 解答 5
递增次序:。至于阈值:、、、,所以 在 时不成立,在 时成立。此后一直成立:若 且 ,则 ,因为 时 。所以 。