康奈尔 CS3110 数据结构与函数式编程讲义（四）

http://adam.chlipala.net/cpdt/* * * 索引 * * * 本页由[coqdoc](http://www.lix.polytechnique.fr/coq/)生成。 # 渐近复杂性的回顾 * * * menu* 渐近分析* 最坏情况和平均情况分析* 增长顺序和大 O 符号* 比较增长顺序* 二叉搜索树* 练习/menu * * * ## 渐近分析 在分析程序的运行时间或空间使用率时我们通常尝试估计时间或空间作为输入大小的函数。例如当分析对数字列表进行排序的函数的最坏情况运行时间时我们将关注它随着输入列表长度的增长而需要多长时间。例如我们说标准插入排序的时间是*T(n)*其中*T(n)c*n*²k*对于某些常数*c*和*k*。相比之下归并排序的时间是*T(*n*)*c***n*log*2k*。 函数*f(n)*例如*f(n)c*n*或*f(n)c*n²*等的**渐近行为**指的是*n*增大时*f(n)*的增长。我们通常忽略*n*的小值因为我们通常只关心对大输入估计程序的速度有多慢。一个好的经验法则是渐近增长率越慢算法越好尽管这通常不是全部。 按照这个标准一个线性算法*即f(n)d*nk*在渐近上总是比二次的好*例如f(n)c*n²q*。这是因为对于任何给定的正*ckd*和*q*总会有一些*n*在这个*n*处*c*n²q*的量级会超过*d*nk*。对于适度的*n*值二次算法很可能比线性算法需要更少的时间例如如果*c*显著小于*d*和/或*k*显著小于*q*。然而对于足够大的输入线性算法总是更好的。在处理渐近增长率时请记得**展望未来**。 ## 最坏情况与平均情况分析 当我们说一个算法的运行时间是*T(n)*时我们的意思是*T(n)*是对运行时间的一个上界对于所有大小为*n*的输入都成立。这称为**最坏情况分析**。该算法在某些大小为*n*的输入上可能需要更少的时间但这无关紧要。如果一个算法对每个大小为*n*的输入只需步骤*T(n)c*n²k*并且对其余输入只需*n*步我们仍然说它是一个二次算法。 替代最坏情况分析的一种流行方法是*平均情况分析*。在这里我们不限制最坏情况的运行时间而是尝试计算在随机选择的输入上花费的期望时间。这种分析通常更难因为它涉及概率论论证并且通常需要对输入分布进行难以证明的假设。另一方面它可能更有用因为有时算法的最坏情况行为会误导性地很差。一个很好的例子是流行的快速排序算法其在长度为*n*的输入序列上的最坏情况运行时间与*n*²成正比但其期望运行时间与*n* log *n*成正比。 ## 增长顺序和大 O 表示法 在估计insert_sort或任何其他程序的运行时间时我们不知道常数*c*或*k*是多少。我们知道它是一个中等大小的常数但除此之外并不重要我们有足够的证据来知道merge_sort见下文比二次的insert_sort更快即使常数可能有所不同。这并不总是成立常数有时会产生影响但一般来说这是一个非常好的经验法则。 我们甚至可能无法直接测量常数*c*。例如我们可能知道语言中的给定表达式比如if需要常数个机器指令但我们可能不知道究竟有多少。此外相同的指令序列在 Pentium IV 上执行的时间将比在 Pentium II 上少尽管差异大致是一个常数因子。因此这些估计通常只准确到一个常数因子。出于这些原因我们通常忽略比较渐近运行时间中的常数因子。 计算机科学家已经开发了一个方便的符号来隐藏常数因子。我们写成*O(n)*读作“阶 *n*”而不是“*cn*是某个常数 *c*”。因此如果存在一个固定的常数*c*对于所有足够大的*n*算法在大小为*n*的输入上最多花费*cn*的时间则称算法为*O(n)*或*线性时间*。如果存在一个固定的常数*c*对于所有足够大的*n*算法在大小为*n*的输入上最多花费*cn²*的时间则称算法为*O(n²)*或*二次时间*。*O(1)*意味着*常数时间*。 *多项式时间*意味着*n^(O(1))*或者*n^c*其中*c*是某个常数。因此任何常数、线性、二次或三次*O(n³)*时间算法都是多项式时间算法。 这被称为*大 O 表示法*。它简洁地捕捉了函数渐近增长率之间的重要差异。 大 O 表示法的一个重要优点是它使得算法分析变得更加容易因为我们可以方便地忽略低阶项。例如一个运行时间为 *10n³ 24n² 3n log n 144* 仍然是一个三次算法因为 *10n³ 24n² 3n log n 144* 10n³ 24n³ 3n³ 144n³ (10 24 3 144)n³ O(n³)*。 当然由于我们忽略了常数因子任何两个线性算法在这个度量标准下都会被认为是同样好的。甚至可能存在一些情况线性算法中的常数太大以至于在实践中即使是具有较小常数的指数算法也可能更可取。这是对渐近分析和大 O 符号的一个有效批评。然而作为一个经验法则它已经为我们服务得很好。只需注意它*仅仅*是一个经验法则--渐近最优算法不一定是最好的。 在复杂度分析中经常见到的一些常见增长阶数是 | *O(1)* | 常数阶 | | --- | --- | | *O(log n)* | 对数阶 | | *O(n)* | 线性阶 | | *O(n log n)* | n log n | | *O(n²)* | 二次阶 | | *O(n³)* | 立方阶 | 这里的*log*表示*log[2]*或以 2 为底的对数尽管对数的底实际上并不重要因为不同底的对数之间只相差一个常数因子。还要注意*2^(O(n))*和*O(2^n)*并不相同 ## 比较增长阶数 **O** 设*f*和*g*是从正整数到正整数的函数。如果*g*是*f*的上界存在一个正常数*c*和一个正整数*n*[0]使得对所有*n≥n*[0] *f(n) ≤ cg(n)*。 同样如果函数*f(n)/g(n)*被某个常数上界限制则*f*是*O(g(n))*。 **o** 我们说*f*是*o(g(n))*读作“f 是 g 的小 o”如果对于所有正常数*c*存在一个正整数*n*[0]使得对所有*n≥n*[0] *f(n) ≤ cg(n)*。 同样如果函数*f(n)/g(n)*随着*n*趋向无穷而趋向于 0则*f*是*o(g)*。也就是说f 相对于 g 来说很小。如果*f*是*o(g)*那么*f*也是*O(g)*。 O 和 o 的定义之间的主要区别在于O 中的上界对于*某个*常数*c*成立而 o 中的上界对于*所有*常数*c*成立。 **Ω** 我们说*f*是Ω(*g*(*n*))读作“f 是 g 的 omega”如果*g*对于大的*n*是*f*的下界。形式上如果存在一个固定常数*c*和一个固定的*n*[0]使得对所有*n**n*[0] *c**g*(*n*) *≤* *f*(*n*) 例如任何最高指数为*n^k*的多项式都是Ω(*n^k*)。如果*f*(*n*)是Ω(*g*(*n*))那么*g(n)*是 O(*f*(*n*))。如果*f*(*n*)是*o*(*g*(*n*))那么*f(n)*不是Ω(*g*(*n*))。 **Θ** 我们说*f*是Θ(*g(n)*)读作“f 是 g 的 theta”如果*g*对于大的*n*是*f*的准确描述它可以被缩放使其既是*f*的上界又是下界。也就是说*f*既是 O(*g*(*n*))又是Ω(*g*(*n*))。展开Ω和*O*的定义如果存在固定常数*c*[1]和*c*[2]以及固定的*n*[0]使得对所有*n**n*[0] *c*[1]*g*(*n*) *≤* *f*(*n*) *≤* *c*[2] *g*(*n*) 例如任何最高指数为 *n^k* 的多项式都是 Θ(*n^k*)。如果 *f* 是 Θ(g)那么它是 *O*(*g*) 但不是 *o*(*g*)。有时人们有点非正式地使用 *O*(*g*(*n*)) 来表示更强的性质 Θ(*g*(*n*))然而这两者是不同的。 这里有一些例子 *n log n* 是 *O(n)* 和 Q(*n*)因为对于所有 *n 1**n* *n log n 2n*。 *n¹⁰⁰⁰* 是 *o(2^n)*因为 *n¹⁰⁰⁰/2^n* 随着 *n* 趋向无穷大而趋向于 0。 对于任意固定但任意小的实数 *c**n log n* 是 *o(n^(1c))*因为 *n log n / n^(1c)* 趋向于 0。为了看到这一点取对数 *log(n log n / n^(1c)) log(n log n) - log(n^(1c)) log n log log n - (1c)log n log log n - c log n* 并观察它趋向于负无穷大。 像 *O*(*n*²) 这样的表达式的含义实际上是一组函数所有 *O*(*n*²) 的函数。当我们说 *f(n)* 是 *O(n*²*)* 时我们的意思是 *f(n)* 是这个集合的一个成员。通常也写成 *f*(*n*) *O*(*g*(*n*))虽然它不是真正的等式。 现在我们介绍一些方便的规则来操作涉及顺序符号的表达式。这些规则我们不加证明地陈述对于处理增长顺序非常有用。它们实际上是关于函数集合的陈述。例如我们可以把 #2 看作是说在 *O*(*f*(*n*)) 和 *O*(*g*(*n*)) 中任意两个函数的乘积也在 *O*(*f*(*n*)*g*(*n*)) 中。 1. *cn^m O(n^k)* 对于任何常数 *c* 和任何 *m ≤ k*。 1. *O(f(n)) O(g(n)) O(f(n) g(n))*。 1. *O(f(n))O(g(n)) O(f(n)g(n))*。 1. *O(cf(n)) O(f(n))* 对于任何常数 *c*。 1. 对于任何常数 *c**c* 是 *O(1)*。 1. *log[b]n O(log n)* 对于任何基数 *b*。 所有这些规则除了#1也适用于 Θ。 * * * ## 练习 1\. 使用列表编写堆栈的实现。每个操作的大 O 运行时间是多少堆栈的签名是module type STACK sigtype a stack val empty : unit - a stack val push : (a * a stack) - a stack val top : a stack - a option val pop : a stack - (a stack) optionend2\. 使用列表编写队列的实现。每个操作的大 O 运行时间是多少队列的签名是module type QUEUE sigtype a queue val empty : unit - a queue val insert : (a * a queue) - a queue val first : a queue - a option val rest : a queue - a optionend3. 手写 List 结构中出现的一些函数例如rev、、map、foldl 等并分析它们以确定它们的大 O 运行时间。** # 第 23 课递归关系 渐近复杂度有其局限性但仍然是分析和改进程序性能的有用工具。使用大 O 符号简化了分析性能的任务。对于 OCaml我们假设在评估过程中执行的所有简化都需要常量时间包括所有算术运算和模式匹配。 如果你从替换模型的角度来思考这个假设可能会让人感到惊讶。替换可能需要大量工作因为替换的变量可能会出现在代码中的许多不同位置。然而OCaml 的实现更接近于求值的环境模型在这种模型中实际的替换从未执行过而是将绑定记录在一个单独的*环境*中以供以后查找。环境可以被实现为所有环境操作包括查找都可以在常数时间内执行。 下面的非负整数乘法例程是正确的但不太高效let rec times1 a b if b 0 then 0else a times1 a (b - 1)作为参数b的大小函数*n*的时间需求的增长顺序是多少注意数字的“大小”可以用它的幅度或数字的位数写下该数字所需的空间来衡量。通常使用位数来衡量但在这里我们使用幅度。请注意写下一个大小为*x*的数字只需要大约*log[10] x*位因此这两个度量是非常不同的。 假设times1函数中的所有原始操作if、、和-以及函数调用的开销都需要常量时间。因此如果*n*0该例程需要一些常量时间*c*[2]。如果*n*0则在大小为*n*的输入上所花费的时间最多为某个常量*c*[1]加上对*n**-*1的递归调用所花费的时间。换句话说存在常量*c*[1]和*c*[2]使得*T(n)*满足T(n) T(n-1) c[1]forn 0T(0) c[2]这是一个**递归关系**或简称**递归**定义了一个函数*T(n)*。它简单地说明了将一个数字*a*乘以另一个大小为*n0*的数字*b*所需的时间是将*a*乘以一个大小为*n-1*的数字的时间再加上一定量的工作执行的原始操作。 递归关系是一个函数的归纳定义。这个特定的递归关系有一个唯一的**闭合形式解**它定义了*T(n)*而不涉及任何递归。为了确定递归函数的运行时间我们将编写描述运行时间的递归找到它们的闭合形式解并用大 O 符号表示这些解。 展开这个特定的递归可以给出如何将其转换为闭合形式的一些思路T(n) T(n-1)c[1]forn 0 *T(n-2)* *c[1]* *c[1]* *T(n-3)* *c[1]* *c[1]* *c[1]* ... *T(n-k)* *kc[1]* for *0 ≤ k ≤ n* ... *T(0)* *nc[1]* for *n ≥ 0* *c[2]* *c[1]n* for *n ≥ 0*即为*O(n)*。 更一般地说我们猜测递归的闭合形式解然后通过归纳证明它成立。有时将递归展开几步可以帮助猜测。 现在考虑另一种乘两个数字的过程let rec times2 a b if b 0 then 0else if even b then times2 (a*2) (b/2)else a times2 a (b-1)再次我们希望用 *n* 的表达式来表示运行时间参数 b 的大小。我们假设双倍和半操作是常数时间的这可以通过算术移位在常数时间内完成以及标准的原语也是常数时间的。对于这个问题递归关系比之前的更复杂T(n) T(n-1) c1 forn 0andnoddT(n) T(n/2) c2 forn 0andnevenT(0) c3我们需要弄清楚这个递归关系的第一分支和第二分支将被执行多少次。如果 *n* 是 2 的幂即如果 *n 2^m* 对于某个整数 *m* 成立那么这就很容易。在这种情况下当 *n* 1 时第二分支只会执行一次因为 *2^m* 是偶数除非 *m* 0即当 *n* 1 时。因此对于这种特殊情况我们可以使用上面的展开技巧得到关于 *m* 的封闭形式T(2^m) T(2^(m-1))c[2]form 0 *T(2^(m-2))* *c[2]* *c[2]* ... *T(2^(m-m))* *mc[2]* *T(1)* *mc[2]* *T(0)* *c[1]* *mc[2]* *c[3]* *c[1]* *mc[2]*这是 *O(log n)*。我们可以通过归纳证明这一点。 ## **强归纳** 强归纳与普通归纳有着相同的步骤你可能还记得来自 CS 2800 的但归纳假设略有不同 1. 陈述待证命题 *P*(*n*) 的形式 1. 基本情况证明 *P*(*n*[0]) 成立 1. 归纳假设假设对于所有 *n*[0] ≤ *m* ≤ *n**P*(*m*) 都成立。这与普通归纳不同普通归纳只假设 *P*(*m*) 对 *m* *n* 成立。 1. 归纳步骤利用归纳假设证明 *P*(*n*1) 成立。 1. 结论*P*(*n*) 对于所有 *n* ≥ *n*[0] 都成立。 我们可以将这个过程形式化为一个推理规则这个规则给了我们证明对于某个谓词 P命题 ∀n.P(n) 的方法。以下分别是弱归纳和强归纳的规则 | **弱归纳** #124; P(0) #124; ∀n (P(n) ⇒ P(n1)) #124; #124; ∀n P(n) #124; | | **强归纳** #124; ∀n (∀m (m n ⇒ P(m)) ⇒ P(n)) #124; #124; ∀n P(n) #124; | | | --- | 注意基本情况在强归纳规则中并没有明确出现。然而它仍然在隐含中存在对于 n0你必须证明 ∀m (m 0 ⇒ P(m)) ⇒ P(0)这可以简化为 P(0)因为∀m (m 0 ⇒ P(m)) 是虚假的因为不存在 m 0。 在实践中通常用强归纳来证明渐近复杂度边界比用弱归纳更容易因为你有一个更强的归纳假设可用即 ∀m m n ⇒ P(m) 而不是 P(n)。然而这两个规则在逻辑上是等价的可以用弱规则证明强规则的有效性其中归纳假设 P(n) ∀m (m n ⇒ P(m))。 ## times2 的运行时间 让我们回到对 times2 的分析。当 *n* 是 2 的幂时我们有以下递归T(n) T(n/2) c2 forn 1andna power of 2T(1) c4 where c4 c3 c1我们用强归纳来证明 *T(n) c[2] log n c[4]* 是这个递归的解。 基本情况*T(1) c[4] c[2] log 1 c[4]*。 归纳假设*T(m) c[2] log m c[4]* 对于所有 *1 ≤ m n* 成立。 归纳步骤 *T(n) T(n/2) c[2]* * c[2] log(n/2) c[4] c[2]* 由 I.H. 推导得出。 * c2 c[4] c[2]* * c[2] log n − c[2] c[4] c[2]* * c[2] log n c[4]*。 因此在输入大小为 *n* 且为 2 的幂的情况下times2 的运行时间为 *O(log n)*。 在一般情况下times2 的运行时间也是 *O(log n)*但我们需要一个稍微不同的递归来更容易地展示这一点。 注意在连续两次递归调用 times2 时参数 b 不可能为奇数因为当它为奇数时会减去一个使其变为偶数。 因此我们可以将原始递归重写为T(n) T((n−1)/2) c[1] c[2]forn 1andnoddT(n) T(n/2) c[2]forn 1andnevenT(1) c4T(0) c3注意这个新的事件与重写代码的情况类似使得两次递归调用都将输入大小减半let rec times3 a b if b 0 then 0else if even b then times3 (a*2) (b/2)else a times3 (a*2) ((b-1)/2)对于这个递归式找到一个封闭形式的解有点困难。 但是使用强归纳我们可以证明无论它是什么对于足够大的常数 *d* 和 *e*它都被形式为 *d log n e* 的函数渐近地界定并且这足以证明解为 *O(log n)*。 因此我们想要通过强归纳来证明 *T(n) ≤ d log n e* 对于一些尚未确定的常数 *d* 和 *e*。 为了找到合适的 *d* 和 *e*我们将直接开始并查看使证明有效的需要什么。 基本情况我们希望 *T(1) c[4] ≤ d log 1 e*。 只要我们选择 *e ≥ c[4]*这就成立。 归纳假设对于所有 *1 ≤ m n**T(m) ≤ d log m e*。 归纳步骤*n* 为偶数 *T(n) T(n/2) c[2]* *≤ d log(n/2) e c[2]* 通过 I.H. * d log n − d e c[2]* *≤ d log n e*只要我们选择 *d ≥ c[2]*。 归纳步骤*n* 为奇数 *T(n) T((n−1)/2) c[1] c[2]* *≤ d log((n−1)/2) e c[1] c[2]* 通过 I.H. * d log(n−1) − d e c[1] c[2]* *≤ d log n − d e c[1] c[2]* *≤ d log n e*只要我们选择 *d ≥ c[1] c[2]*。 选择足够大的 *d* 和 *e* 来满足所有这些条件我们看到 *T(n) ≤ (c[1] c[2]) log n c[4]* 对于所有 *n ≥ 1* 成立因此 *T(n)* 是 *O(log n)*。 # 讲座 25摊销分析 哈希表具有*O*(1)的期望性能用于查找和插入的断言基于这样一个假设存储在表中的元素数量与桶的数量相当。如果哈希表的元素比桶多得多则存储在每个桶中的元素数量将变大。例如如果桶的数量是常数并且有*O*(*n*)个元素则查找时间是*O*(*n*)而不是*O*(1)。 这个问题的解决方法是当表中元素的数量与表的大小相比变得太大时增加表的大小。如果我们将def负载因子/def定义为元素数与桶数的比率当负载因子超过某个小常数通常对于链接为 2对于线性探查为 0.75时我们会分配一个新表通常是旧表大小的两倍并将所有元素重新哈希到新表中。这个操作不是恒定时间的而是与表增长时的元素数量成线性关系。 调整大小操作的线性运行时间并不像听起来的那么严重尽管对于某些实时计算系统可能会有问题。如果表每次需要时都增加两倍大小那么调整大小操作的频率将指数级下降。因此将*n*个元素插入空数组仅需要*O*(*n*)的时间包括调整大小的成本。我们说插入操作具有*O*(1) def摊销运行时间/def因为插入元素所需的时间*平均*为*O*(1)即使有些元素会触发对哈希表的所有元素进行长时间的重新哈希。 数组大小以几何级增长倍增至关重要。固定增量增长数组例如每次增加 100 个元素可能很诱人但这会导致渐近线性而不是恒定的摊销运行时间。 现在我们转向对摊销分析的更详细描述。 ## 摊销分析 摊销分析是对一系列操作的最坏情况分析旨在得到比单独分析序列中的每个操作更紧密的整体或平均每个操作的成本界限。例如当我们考虑前面学期对不相交集数据抽象的并集和查找操作时我们能够将单个操作的运行时间限制在*O*(log *n*)。然而对于一个包含*n*个操作的序列可以获得比*O*(*n* log *n*)更紧密的界限尽管该分析更适用于 4820 而不是这门课程。在这里我们将考虑上述哈希表问题的简化版本并展示*n*个插入操作的序列具有总时间*O*(*n*)。 摊销分析使用了三种主要技术 def聚合方法/def即分析一系列操作的总运行时间。 def记账/def或def银行家/def方法我们对廉价操作施加额外费用然后用它来支付后续昂贵的操作。 def潜力/def或def物理学家/def方法我们通过导出描述我们每一步可以额外完成的工作量的*潜力函数*来进行。该潜力函数随着每一次操作的进行而增加或减少但不能为负。 考虑一个可以存储任意数量整数的可扩展数组如 Java 中的ArrayList或Vector。这些是以普通非可扩展数组来实现的。每次add操作都在之前插入的所有元素之后插入一个新元素。如果没有剩余的空单元就会分配一个大小加倍的新数组并且所有旧数组中的数据都复制到新数组的相应条目中。例如考虑以下一系列插入从长度为 1 的数组开始--Insert 11 |11|-- ----Insert 12 |11|12|---- --------Insert 13 |11|12|13| |-------- --------Insert 14 |11|12|13|14|-------- ----------------Insert 15 |11|12|13|14|15| | | |----------------表在第二、第三和第五步中加倍。由于在最坏情况下每次插入都需要*O*(*n*)的时间所以简单的分析会得出*n*次插入的*O*(*n*²)时间界限。但情况并非如此糟糕。让我们使用三种方法分析一个*n*次操作的序列。 ### 累积法 让*c[i]*表示第*i*次插入的成本c[i]iifi−1is a power of 21 otherwise让我们考虑序列中前几次插入的表大小*s[i]*和成本*c[i]*i1 2 3 4 5 6 7 8 9 10s[i]1 2 4 4 8 8 8 8 16 16c[i]1 2 3 1 5 1 1 1 9 1或者我们可以看到*c[i]*1*d[i]*其中*d[i]*是表大小加倍的成本。也就是说d[i]i−1ifi−1is a power of 20 otherwise然后在整个序列上求和所有的 1 都加起来得到*O*(*n*)而所有的*d[i]*也加起来得到*O*(*n*)。也就是说Σ*[1≤i≤n] c[i]* ≤ n Σ*[0≤j≤m] 2^(j−1)*其中*m* log(*n* − 1)。不等式右边的两个项都是*O*(*n*)因此*n*次插入的总运行时间为*O*(*n*)。 ### 记账银行家法 累积法直接寻求对一系列操作的总体运行时间的界限。相比之下记账法试图找到对每个个别操作收取的额外时间单位的*支付*使得这些支付的总和是总实际成本的上界。直观地说我们可以想象维护一个银行账户。低成本操作的收费略高于其真实成本并且剩余部分存入银行账户以备将来使用。然后可以将高成本操作的收费低于其真实成本并且透支是由银行账户中的储蓄支付的。通过这种方式我们将高成本操作的成本分摊到整个序列中。对每个操作的收费必须设置得足够大以确保银行账户的余额始终保持正数但又不能太大以至于没有一个操作的收费明显高于其实际成本。 我们强调对操作额外计费并不意味着该操作实际花费了那么多时间。这只是一种使分析更容易的记账方法。 如果我们让*c[i]*是第*i*个操作的费用*c[i]*是真实的费用那么我们希望 Σ*[1≤i≤n] c[i]* ≤ Σ*[1≤i≤n] c[i]* 对于所有的*n*这意味着*n*个操作序列的def分摊时间/def Σ*[1≤i≤n] c[i]* 是对真实时间 Σ*[1≤i≤n] c[i]* 的一个上界。 回到可扩展数组的示例。假设插入一个元素花费 1 个单位当表扩大时移动它花费 1 个单位。显然每次插入 1 个单位的费用不够因为没有剩余的费用来支付移动费用。每次插入 2 个单位的费用还不够但是每次插入 3 个单位似乎足够i1 2 3 4 5 6 7 8 9 10s[i]1 2 4 4 8 8 8 8 16 16c[i]1 2 3 1 5 1 1 1 9 1c’[i]3 3 3 3 3 3 3 3 3 3b[i]2 3 3 5 3 5 7 9 3 5其中*b[i]*是第*i*次插入后的余额。 实际上这在一般情况下就足够了。让*m*指代第*m*个插入的元素。对*m*收取的三个单位被用于以下目的 一个单位用于立即将*m*插入表中。 一个单位用于在插入*m*后第一次扩大表时移动*m*。 一个单位捐赠给元素*m − 2^k*其中*2^k*是不超过*m*的最大 2 的幂并且用于在插入*m*后第一次扩大表时移动该元素。 现在每当一个元素被移动时移动费用已经付清。第一次移动元素时它是由插入时向其收取的一个自己的时间单位付费的所有后续的移动都是由后来插入的元素的捐赠支付的。 实际上我们可以做得更好一点只收取第一次插入的费用为 1然后对每次插入后的插入收取 3 个单位的费用因为对于第一次插入没有要复制的元素。这将在第一次插入后产生零余额然后在此后产生正余额。 ### 势物理学家方法 在上面我们看到了处理可扩展数组的聚合方法和银行家方法。现在让我们来看看物理学家的方法。 假设我们可以在数据结构的状态上定义一个def势函数/defΦ读作“Phi”具有以下特性 Φ(*h*[0]) 0其中*h*[0]是数据结构的初始状态。 对于计算过程中出现的数据结构的所有状态*h*[*t*]都有Φ(*h*[*t*]) ≥ 0。 直观地势函数将跟踪计算中任意点的预充值时间。它衡量了有多少积累的时间可用于支付昂贵的操作。这类似于银行家法中的银行余额。但有趣的是它仅取决于数据结构的当前状态而不考虑使其处于该状态的计算历史。 我们将一个操作的*分摊时间*定义为 *c* Φ(*h*) − Φ(*h*), 其中*c*是操作的实际成本*h*和*h*是操作之前和之后的数据结构状态。因此摊销时间是实际时间加上潜力变化。理想情况下Φ应该被定义为每个操作的摊销时间很小。因此潜力变化对于低成本操作应该是正的对于高成本操作应该是负的。 现在考虑一系列*n*个操作实际花费时间为*c*[0]*c*[1]*c*[2]...*c*[*n*−1]并产生数据结构*h*[1]*h*[2]...*h*[*n*]从*h*[0]开始。总摊销时间是单个摊销时间的总和 (*c*[0] Φ(*h*[1]) − Φ(*h*[0])) (*c*[1] Φ(*h*[2]) − Φ(*h*[1])) ... (*c*[*n*−1] Φ(*h*[*n*]) − Φ(*h*[*n*−1])) *c*[0] *c*[1] ... *c*[*n*−1] Φ(*h*[*n*]) − Φ(*h*[0]) *c*[0] *c*[1] ... *c*[*n*−1] Φ(*h*[*n*])。 因此一系列操作的摊销时间高估了Φ(*h*[*n*])假设Φ始终为正。因此总摊销时间始终是实际时间的上界。 对于动态可调整大小的数组通过加倍调整大小我们可以使用潜力函数 Φ(*h*) 2*n* − *m* 其中*n*是当前元素的数量*m*是数组的当前长度。如果我们从长度为 0 的数组开始并在添加第一个元素时分配长度为 1 的数组然后每当需要更多空间时都将数组大小加倍我们有Φ(*h*[0]) 0并且Φ(*h*[*t*]) ≥ 0 对于所有*t*都成立。后者不等式成立因为元素的数量始终至少是数组大小的一半。 现在我们想要证明添加元素的摊销时间是常数时间。有两种情况。 如果*n* *m*那么实际成本是 1*n*增加 1*m*不变。然后潜力增加 2因此摊销时间为 1 2 3。 如果*n* *m*那么数组加倍因此实际时间是*n* 1。但是潜力从*n*下降到 2所以摊销时间是*n* 1 (2 − *n*) 3。 在两种情况下摊销时间都是 O(1)。 用物理学家的方法进行摊销分析的关键是定义正确的潜力函数。潜力函数需要保存足够的时间在需要时使用。但是它不能保存太多的时间以致导致当前操作的摊销时间过高。 # 第 24 讲解决递归关系 在上一讲中我们看到了如何解决递归关系的方法以一个简单的乘法函数作为例子该函数只使用加法并在时间上运行为*O(log n)*。今天我们将通过证明归并排序的复杂性以及计算斐波那契数的函数的复杂性来看更多的例子。 ## 归并排序 ### 归并排序的实现let rec split (l: a list) : a list * a list match l with[] - [],[]| [x] - [x],[]| x::y::t - let l,rsplit t in x::l,y::r(* A simpler way to write split. Recall the definition ofList.fold_right. What is the asymptotic performance ofList.fold_right f lst acc0 where f is an O(1) functionand lst is an n-element list? O(n). *)let split’ (l: a list) : a list * a list List.fold_right (fun x (left,right) - (x::right,left)) l ([],[])let rec merge (left: a list) (right: a list): a list match (left, right) with([],_) - right| (_,[]) - left| (x::rest_left, y::rest_right) -if x y then y::(merge left rest_right) else x::(merge rest_left right)(* merge_sort l is a list containing the same elements as xs but inascending (nondescending) sorted order. *)let rec merge_sort (l: a list) : a list (* Implementation: lists of size 0 or 1 are already sorted. Otherwise,split the list into two lists of equal size, recursively sortthem, and then merge the two lists back together. *)match l with([]|[_]) - l| _ - let (left, right) split l inmerge (merge_sort left) (merge_sort right)### 归并排序渐近时间复杂度分析 现在让我们展示merge_sort不仅是一个*正确*的算法而且是一个*高效*的排序数字列表的算法。我们首先观察到没有证明的情况下split函数的性能与输入列表的大小成线性关系。这可以通过与我们将对merge采取的相同方法来证明因此我们只看merge。 merge函数的运行时间也是线性的—也就是*O*(*n*)—在两个输入列表的总长度上。我们首先找出执行时间的递归关系。假设输入列表的总长度为零或一。那么函数必须执行 case 表达式的两个*O*(1)分支之一。这些最多花费一些时间*c*[0]来执行。所以我们有 *T*(0) *c*[0] *T*(1) *c*[0] 现在考虑总长度为*n*的列表。递归调用的列表总长度为*n*−1因此我们有 *T*(*n*) *T*(*n*−1) *c*[1] 这里*c*[1]是对执行 if 语句和操作符::对于列表的常规实现需要常数时间所需时间的常数上界。这给了我们一个解决*T*的递归关系的递归关系。我们可以通过展开前几个步骤的递归关系不等式来应用迭代方法来解决递归关系。 *T*(0) *c*[0] *T*(1) *c*[0] *T*(2) *T*(1) *c*[1] *c*[0] *c*[1] *T*(3) *T*(2) *c*[1] *c*[0] 2*c*[1] *T*(4) *T*(3) *c*[1] *c*[0] 3*c*[1 ...] *T*(*n*) *T*(*n*−1) *c*[1] *c*[0] (*n*−1)*c*[1] (*c*[0] - c[1]) *c*[1]*n* 我们注意到最后一行捕捉到的模式。这种模式可以通过归纳更严谨地证明让我们归纳地证明对于*n 0**T*(*n*)(*c*[0] - c[1]) *c*[1]*n*。对于*n0*结果是正确的以上已证明如果对于*n-1*成立则使用上面的最后一行对于 n 也是成立的。 回想一下如果对于所有大于某个*n*[0]的*n*我们可以找到一个常数*k*使得*T*(*n*) *kn*那么*T*(*n*)是*O*(*n*)。 对于至少为 1 的*n*通过设置*k* *c*[0] 2*c*[1]这很容易满足。或者我们可以记住任何一次多项式都是*O*(*n*)也是Θ(*n*)。找到正确的界限的更简单的方法是观察常数*c[0]*和*c[1]*的选择并不重要如果我们将它们都替换为 1我们得到*T*(1) 1*T*(2)2*T*(3)3 等这显然是*O*(*n*)。 现在让我们考虑merge_sort函数本身。同样地对于零个和一个元素的列表我们在常数时间内计算。对于 *n* 个元素的列表我们进行两次递归调用但是对大约一半大小的子列表进行调用以及对于每个都需要Θ(*n*)时间的split和merge。为简单起见我们假装子列表的大小正好是一半。我们获得的递归关系形式如下 *T*(0) *c*[0] *T*(1) *c*[0] *T*(*n*) 2 *T*(*n*/2) *c*[1]*n * *c*[2]*n c*[3] 让我们使用迭代法来计算merge_sort的运行时间。我们知道任何解决方案都必须适用于任意常数 *c*[0] 和 *c*[4]所以我们再次将它们都替换为 1 以保持简单。这样我们就得到以下递归方程 *T*(1) 1 *T*(*n*) 2 *T*(*n*/2) *n* 从迭代法开始我们可以开始展开时间方程直到注意到一种模式 *T*(*n*) 2*T*(*n*/2) *n* 2(2*T*(*n*/4) *n*/2) *n* 4*T*(*n*/4) *n* *n* 4(2*T*(*n*/8) *n*/4) *n* *n* 8*T*(*n*/8) *n* *n* *n* *nT*(*n*/*n*) *n* ... *n* *n* *n* *n* *n* ... *n* *n* *n* 计算最后的总和中 *n* 的重复次数我们看到它们有 lg *n* 1 个。 因此运行时间为 *n*(lg *n* 1) *n* lg *n* *n*。我们观察到 *n* lg *n* *n* *n* lg *n* *n* lg *n* 2*n* lg *n* 对于 *n*0所以运行时间是 *O*(*n* lg *n*)。 现在我们已经通过迭代方法进行了分析让我们使用强归纳来验证这个界限是否正确。 ### 使用强归纳的归并排序分析 **要证明的性质 P(n)** *n* ≥ 1 ⇒ *T*(*n*) *n* lg *n* *n* **对于 n 进行强函数值归纳**。对于任意的 *n*假设归纳假设 *T*(*m*) *m* lg *m* *m* 对于所有的 *m**n* 是真实的。 **情况 n 0**空证 **情况 n 1**T(1) 1 1 lg 1 1 **情况 n 1** 归纳假设 证明 *T*(*n*) 2 T(*n*/2) *n* (*n*/2) lg (*n*/2) 2(*n*/2) *n* *(根据归纳假设)* *n* lg (*n*/2) 2*n* *n* lg *n* − 1) 1) 2*n* *n* lg *n* *n* 由于 *n* lg *n* *n* 是Θ(*n* lg *n*)我们已经证明了归并排序是Θ(*n* lg *n*)。 ## 斐波那契数 斐波那契数记作*F(n)*由*F(0)0**F(1)1*定义对于*n1**F(n)F(n-1)F(n-2)*。 前几个斐波那契数是 0,1,1,2,3,5,8,13,21,34,55,89,... ### 第一个实现版本及其复杂度 我们想要编写一个计算第 *n* 个斐波那契数的函数。 第一个实现版本可能是(* requires n0 *)let rec fibofunction0 - 0| 1 - 1| n - (fibo (n-1))(fibo (n-2))此函数直接遵循斐波那契数的定义因此它的正确性是显而易见的。现在如果我们尝试在 OCaml 中运行它比如说 100它需要永远的时间才能完成。让我们通过分析其渐近时间来看看为什么。 当*n0*和*n1*时的渐近时间是常数我们称之为*c[0]*因此*T(0)T(1)c[0]*。为了计算*T(n)*我们进行两次递归调用得到*T(n)T(n-1)T(n-2)*。 在数学中可以证明这个递推关系的解的形式是 *T(n)a[1]*r[1]^na[2]*r[2]^n*其中 *r[1]* 和 *r[2]* 是方程 *r²r1* 的解。我们得到 *r[1](1sqrt(5))/2* 和 *r[2](1-sqrt(5))/2*。然后根据 *T(0)T(1)c[0]*我们得到 *a[1]a[2]a[1]r[1]a[2]r[2]c[0]*从而得到 *a[1]c[0]r[1]/sqrt(5)* 和 *a[2]-c[0]r[2]/sqrt(5)*。 我们可以看到 *r[2]1*因此 *r[2]^n* 是 *o(1)*。因此 *T(n)* 是 *Θ(r[1]^n)*其中 *r[1](1sqrt(5))/2*。因此算法完成所需的时间是指数级的。 ### 更高效的实现方式(* requires n0 *)let fibo’ nif(n0) then 0 else(* a is F(i-2) and b is F(i-1) *)let aref 0 and bref 1 and cref 0 infor i2 to n doc: !b; b: !a !b; a: !c;done; !b这个实现显然是线性的每次循环需要固定的时间完成循环次数是*n*的数量级。与之前一样正确性可以通过对*n*进行递归来得到声明在每次循环中*aF(i-2)* 和 *bF(i-1)*。