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*2+k'*。 函数*f(n)*（例如*f(n)=c*n*或*f(n)=c*n²*等）的**渐近行为**指的是*n*增大时*f(n)*的增长。我们通常忽略*n*的小值，因为我们通常只关心对大输入估计程序的速度有多慢。一个好的经验法则是：渐近增长率越慢，算法越好（尽管这通常不是全部）。 按照这个标准，一个线性算法（*即，f(n)=d*n+k*）在渐近上总是比二次的好（*例如，f(n)=c*n²+q*）。这是因为对于任何给定的（正）*c，k，d*和*q*，总会有一些*n*，在这个*n*处，*c*n²+q*的量级会超过*d*n+k*。对于适度的*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^(1+c))*，因为 *n log n / n^(1+c)* 趋向于 0。为了看到这一点，取对数 *log(n log n / n^(1+c)) = log(n log n) - log(n^(1+c)) = log n + log log n - (1+c)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 =
sig
type '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) optionend
2\. 使用列表编写队列的实现。每个操作的大 O 运行时间是多少？队列的签名是：module type QUEUE =
sig
type '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 optionend
3. 手写 List 结构中出现的一些函数（例如，rev、@、map、foldl 等），并分析它们以确定它们的大 O 运行时间。** # 第 23 课：递归关系 渐近复杂度有其局限性，但仍然是分析和改进程序性能的有用工具。使用大 O 符号简化了分析性能的任务。对于 OCaml，我们假设在评估过程中执行的所有简化都需要常量时间，包括所有算术运算和模式匹配。 如果你从替换模型的角度来思考，这个假设可能会让人感到惊讶。替换可能需要大量工作，因为替换的变量可能会出现在代码中的许多不同位置。然而，OCaml 的实现更接近于求值的环境模型，在这种模型中，实际的替换从未执行过，而是将绑定记录在一个单独的*环境*中以供以后查找。环境可以被实现为所有环境操作（包括查找）都可以在常数时间内执行。 下面的非负整数乘法例程是正确的，但不太高效：let rec times1 a b =
if b = 0 then 0
else 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 > 0
T(0) = c[2]
这是一个**递归关系**（或简称**递归**），定义了一个函数*T(n)*。它简单地说明了将一个数字*a*乘以另一个大小为*n>0*的数字*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 0
else if even b then times2 (a*2) (b/2)
else a + times2 a (b-1)
再次，我们希望用 *n* 的表达式来表示运行时间，参数 `b` 的大小。我们假设双倍和半操作是常数时间的（这可以通过算术移位在常数时间内完成），以及标准的原语也是常数时间的。对于这个问题，递归关系比之前的更复杂：T(n) = T(n-1) + c1 forn > 0andnodd
T(n) = T(n/2) + c2 forn > 0andneven
T(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) 的方法。以下分别是弱归纳和强归纳的规则： | **弱归纳：** | P(0) | ∀n (P(n) ⇒ P(n+1)) | | ∀n P(n) | | | **强归纳：** | ∀n (∀m (m < n ⇒ P(m)) ⇒ P(n)) | | ∀n P(n) | | | | --- | 注意，基本情况在强归纳规则中并没有明确出现。然而，它仍然在隐含中存在：对于 n=0，你必须证明 ∀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 2
T(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 > 1andnodd
T(n) = T(n/2) + c[2]forn > 1andneven
T(1) = c4
T(0) = c3
注意，这个新的事件与重写代码的情况类似，使得两次递归调用都将输入大小减半：let rec times3 a b =
if b = 0 then 0
else 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 2
1 otherwise让我们考虑序列中前几次插入的表大小*s[i]*和成本*c[i]*：i1 2 3 4 5 6 7 8 9 10
s[i]1 2 4 4 8 8 8 8 16 16
c[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 2
0 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 10
s[i]1 2 4 4 8 8 8 8 16 16
c[i]1 2 3 1 5 1 1 1 9 1
c’[i]3 3 3 3 3 3 3 3 3 3
b[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,r=split t in x::l,y::r
(* A simpler way to write split. Recall the definition of
List.fold_right. What is the asymptotic performance of
List.fold_right f lst acc0 where f is an O(1) function
and 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 in
- ascending (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 sort
them, and then merge the two lists back together. *)
match l with
([]|[_]) -> l
| _ -> let (left, right) = split l in
merge (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*。对于*n=0*，结果是正确的（以上已证明），如果对于*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*定义，对于*n>1*，*F(n)=F(n-1)+F(n-2)*。 前几个斐波那契数是 0,1,1,2,3,5,8,13,21,34,55,89,... ### 第一个实现版本及其复杂度 我们想要编写一个计算第 *n* 个斐波那契数的函数。 第一个实现版本可能是：(* requires n>=0 *)
let rec fibo=function
0 -> 0
| 1 -> 1
| n -> (fibo (n-1))+(fibo (n-2))
此函数直接遵循斐波那契数的定义，因此它的正确性是显而易见的。现在，如果我们尝试在 OCaml 中运行它，比如说 100，它需要永远的时间才能完成。让我们通过分析其渐近时间来看看为什么。 当*n=0*和*n=1*时的渐近时间是常数，我们称之为*c[0]*，因此*T(0)=T(1)=c[0]*。为了计算*T(n)*，我们进行两次递归调用，得到*T(n)=T(n-1)+T(n-2)*。 在数学中，可以证明这个递推关系的解的形式是 *T(n)=a[1]*r[1]^n+a[2]*r[2]^n*，其中 *r[1]* 和 *r[2]* 是方程 *r²=r+1* 的解。我们得到 *r[1]=(1+sqrt(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]=(1+sqrt(5))/2*。因此算法完成所需的时间是指数级的。 ### 更高效的实现方式(* requires n>=0 *)
let fibo’ n=
if(n=0) then 0 else
(* a is F(i-2) and b is F(i-1) *)
let a=ref 0 and b=ref 1 and c=ref 0 in
for i=2 to n do
c:= !b; b:= !a + !b; a:= !c;done; !b
这个实现显然是线性的：每次循环需要固定的时间完成，循环次数是*n*的数量级。与之前一样，正确性可以通过对*n*进行递归来得到（声明在每次循环中，*a=F(i-2)* 和 *b=F(i-1)*）。
