2.3 设计算法

一. 分治法

1.增量方法

  插入排序使用了增量方法：   在排序子数组A[1 . . j - 1]后，将单个元素A[j]插入子数组的适当位置，产生排序好的子数组A[1 . . j]。

2.分治法

  Ⅰ.递归：   为了解决一个给定的问题，算法一次或者多次地递归调用其自身已解决紧密相关的若干子问题。   这些算法典型地遵循分治法的思想：将原问题分解为几个规模较小但类似原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

  Ⅱ.分治模式在每层递归时都有三个步骤：   ①.分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。   ②.解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。   ③.合并这些子问题的解成原问题的解。

  Ⅲ.归并算法完全遵循分治模式，直观上其操作如下：   分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。   解决：使用归并排序递归地排序两个字序列。   合并：合并两个已排序的子序列已产生已排序的答案。   当待排序的序列长度为1时，递归“开始回升”，在这种情况下不要做任何工作，因为长度为1的每个序列都已排好序。

  Ⅳ.归并排序算法的关键操作是“合并”步骤中两个已排序序列的合并。我们通过调用一个辅助过程MERGE(A, p, q, r)来完成合并，p<=q<r。   过程MERGE需要Θ(n)的时间，其中n=r-p+1是待合并元素的总数。

  Ⅴ.为了避免每个步骤必须检查是否有待排序数组取出后已变为空，可在每个堆的底部放置一张哨兵牌。

  Ⅵ.

MERGE(A, p, q, r)

n1 = q - p + 1 n2 = r - p let L[1 .. n1 + 1] and R[1 .. n2 + 1] be new arrays for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = ∞ R[n2 + 1] = ∞ i = 1 j = 1 for k = p to r if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1

  Ⅵ.上述伪代码中第10~17行，通过维持以下循环不变式，执行r-p+1个基本步骤：   在开始第12~17行for循环的每次迭代时，子数组A[p . . k - 1]按从小到大的顺序包含L[1 . . n1 + 1]和R[1 . . n2 + 1]中的k - p个最小元素。进而，L[i]和R[j]是各自所在数组中未被复制回数组A的最小元素。   我们必须证明第12~17行for循环的第一次迭代之前该循环不变式成立，该循环的每次迭代保持该不变式，并且循环终止时，该不变式提供了一种有用的性质来证明正确性。   初始化：循环的第一次迭代之前，有k = p，所以子数组A[p . . k - 1]为空。这个空的子数组包含L和R的k - p = 0个最小元素。又因为i = j = 1，所以L[i]和R[j]都是各自所在数组中未被复制回数组A的最小元素。   保持：为了理解每次迭代都维持循环不变式，首先假设L[i]<=R[j]。这时，L[i]是未被复制回数组A的最小元素。因为A[p . . k - 1]包含k - p个最小元素，所以在第14行将L[i]复制到A[k]之后，子数组A[p . . k]将包含k - p +1个最小元素。增加k的值（在for循环中更新）和i的值（在第15行中）后，为下次迭代重新建立了循环不变式。反之，若L[i] > R[j]，则第16~17行执行适当的操作来维持循环不变式。   终止：终止时k = r + 1,。根据循环不变式，子数组A[p . . k - 1]就是A[p . . r]且按照从小到大的顺序包含L[1 . . n₁ + 1]和R[1 . . n₂ + 1]中的k - p = r - p + 1个最小元素。数组L和R一起包含n₁ + n₂ + 2 = r - p + 3个元素。除两个最大的元素以外，其他所有元素都已被复制回数组A，这两个最大的元素就是哨兵。

  Ⅶ.

MERGE-SORT(A, p, r)

if p < r q = ⌊(p + r) / 2⌋ MERGE-SORT(A, p, q) MERGE-SORT(A, q + 1, r) MERGE(A, p, q, r)

3.分析分治算法

  Ⅰ.当一个算法包含对其自身的递归调用时可以用递归方程或递归式来描述其运行时间，该方程根据在较小输入上的运行时间来描述在规模为n的问题上的总运行时间。

  Ⅱ.分治算法运行时间的递归式来自基本模式的三个步骤：   假设 T(n)为规模为n的一个问题的运行时间。如果问题规模足够小，如对某个常量 c，n <= c ，则直接求解需要常量时间，我们将其写作 Θ(1)。   假设把原问题分解成 a 个子问题，每个子问题的规模是原问题的 1/b 。为了求解一个规模为 n/b 的子问题，需要 T(n / b) 的时间，所以需要 aT(n / b) 的时间来求解 a 个子问题。如果分解问题成子问题需要时间 D(n) ，合并子问题的解成原问题的解需要时间 C(n) ，那么得到递归式：    $$T(n)=\{\begin{array}{ll}\Theta (1),& \text{若n <= c}\\ aT(\frac{n}{b})+D(n)+C(n),& \text{其他}\end{array}$$

  Ⅲ.分析建立归并排序n个数的最坏情况运行时间T(n)的递归式。归并排序一个元素需要常数时间。当有n > 1个元素时，分解运行时间如下：   分解：分解步骤仅仅计算子数组的中间位置，需要常量时间，因此，D(n) = Θ(1)。   解决：递归地求解两个规模均为n / 2的子问题，将贡献2T(n/2)的运行时间。   合并：在一个具有n个元素的子数组上过程MERGE需要Θ(n)的时间，所以C(n) = Θ(n)。

  Ⅳ.最坏情况下，归并排序的最坏情况运行时间T(n)的递归式： $$T(n)=\{\begin{array}{ll}\Theta (1),& \text{若n = 1}\\ 2T(\frac{n}{2})+\Theta (n),& \text{若n > 1}\end{array}$$

  其实 T(n) 可以用“主定理”证明为 Θ(nlgn)，其中 lgn 为 log₂n。   故对于足够大的输入，在最坏情况下，运行时间为Θ(nlgn)的归并排序将优于运行时间为Θ(n²)的插入排序。

  Ⅴ.以递归树的形式分析复杂度，将T(n)重写为： $$T(n)=\{\begin{array}{ll}\Theta (1),& \text{若n = 1}\\ 2T(\frac{n}{2})+cn,& \text{若n > 1}\end{array}$$

  易得总代价为cn(lgn + 1)，忽略低阶项和常量c可得结果。

4.分治算法的实现

  Ⅰ.C语言版

#include <stdio.h> #define N 10000 #define Max 0x7fffffff int b[N]; int c[N]; void Merge(int a[], int p, int q, int r) { int n1 = q - p + 1; int n2 = r - q; for (int i = 0; i < n1; ++i) { b[i] = a[p + i]; } for (int j = 0; j < n2; ++j) { c[j] = a[q + 1 + j]; } b[n1] = Max; c[n2] = Max; int i = 0; int j = 0; for (int k = p; k <= r; ++k) { if (b[i] <= c[j]) { a[k] = b[i]; i++; } else{ a[k] = c[j]; j++; } } } void Merge_Sort(int a[], int p, int r) { if (p < r) { int q = (p + r) / 2; Merge_Sort(a, p, q); Merge_Sort(a, q + 1, r); Merge(a, p, q, r);; } return; } int main() { int n; scanf("%d", &n); int a[N]; for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); } Merge_Sort(a, 0, n - 1); for (int i = 0; i < n; ++i) { printf("%d ", a[i]); } printf("\n"); return 0; }

二.课后习题

2.3-1

  使用图2-4作为模型，说明归并排序在数组A=<3, 41, 52, 26, 38, 57, 9, 49>上的操作。

略

2.3-2

  重写过程MERGE，使之不用哨兵，而是一旦数组L或R的所有元素均被复制回A就立刻停止，然后把另一个数组的剩余部分复制回A。

MERGE(A, p, q, r)

n1 = q - p + 1 n2 = r - p let L[1 .. n1 + 1] and R[1 .. n2 + 1] be new arrays for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] i = 1 j = 1 for k = p to r if i >= n1 A[k] = R[j] j = j + 1 else if j >= n2 A[k] = L[i] i = i + 1 else if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1

2.3-3

  使用数学归纳法证明：当n刚好是2的幂时，以下递归式的解是T(n) = nlgn。 $$T(n)=\{\begin{array}{ll}2,& \text{若n = 2}\\ 2T(\frac{n}{2})+n,& \text{若n = 2k, k > 1}\end{array}$$

证明： 当n = 2时，T(n) = 2 = 2 * lg2 假设n <= 2^k 假设均成立 当n = 2^k+1 时，由归纳假设T(2^k+1) = 2T(2^k) + 2 ^k+1 = 2 * 2^k * k + 2 ^k+1 = k * 2 ^k+1从而当n = 2^k+1 时假设成立 证毕

2.3-4

  我们可以把插入排序表示为如下的一个递归过程。为了排序A[1 . . n]，我们递归地排序A[1 . . n - 1]，然后把A[n]插入已排序的数组A[1 . . n - 1]。为插入排序的这个递归版本的最坏情况运行时间写一个递归式。

  插入排序的伪代码：

INSERTSORT(A, n)

if(n > 1) INSERTSORT(A, n - 1) INSERT(A, n)

INSERT(A, n)

i = n - 1 key = A[n] while i > 0 and A[i] > key A[i + 1] = A[i] i = i - 1 A[i + 1] = key

  其C语言代码如下：

#include <stdio.h> #define N 10000 void Insert(int a[],int n) { int i = n - 1; int key = a[n]; while(i >= 0 && a[i] > key) { a[i + 1]= a[i]; i--; } a[i + 1] = key; } void InsertSort(int a[],int n) { if(n > 0){ InsertSort(a, n - 1); Insert(a, n); } } int main() { int n; scanf("%d", &n); int a[N]; for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); } InsertSort(a, n - 1); for (int i = 0; i < n; ++i) { printf("%d ", a[i]); } printf("\n"); return 0; }

  故时间复杂度探究如下： $$T(n)=\{\begin{array}{ll}\Theta (1),& \text{若n = 1 或者 n = 2}\\ T(n-1)+\Theta (n),& \text{其他}\end{array}$$

2.3-5

  回顾查找问题（参见练习2.1-3）。注意到，如果序列A已排好序，就可以将该序列的中点与v进行比较。根据比较的结果，原序列中有一半就可以不用再做进一步的考虑了。二分查找算法重复这个过程，每次都将序列剩余部分的规模减半。为二分查找写出迭代或递归的伪代码。证明：二分查找的最坏情况运行时间为Θ（lgn）。

  迭代的伪代码：

BINARYSEARCH(A, v)

l = 1 r = n while l < r q = (l + r) / 2 if A[q] < v l = q + 1 else if A[q] > v r = q - 1 else return q

  C语言版本：

#include <stdio.h> int BinarySort(int a[], int n) { int l = 0; int r = 9; while (l < r) { int q = (l + r) / 2; if (a[q] == n) { return q; } else if (a[q] > n) { r = q - 1; } else if (a[q] < n) { l = q + 1; } } } int main() { int a[10] = { 1, 2, 5, 7, 11, 56, 78, 99,123,546 }; int n; scanf("%d", &n); printf("%d\n", BinarySort(a, n)); return 0; }

  递归的伪代码：

BINARYSEARCH(A, p, q, v)

if(p > q) return NIL r = (p + q) / 2 if(A[r] = v) return q else if(A[r] > v) BINARYSEARCH(A, p, q - 1, v) else if(A[r] < v) BINARYSEARCH(A, p + 1, q, v)

  C语言版本：

#include <stdio.h> int BinarySort(int a[], int p, int q, int v) { if(p > q) return -1; int r = (p + q) / 2 if(A[r] == v) return q; else if(A[r] > v) return BinarySort(A, p, q - 1, v); else if(A[r] < v) return BinarySort(A, p + 1, q, v); } int main() { int a[10] = { 1, 2, 5, 7, 11, 56, 78, 99,123,546 }; int n; scanf("%d", &n); printf("%d\n", BinarySort(a, 0, 9, n)); return 0; }

  证明如下：

由于二分查找每次将问题所用的有序数据划分为一半的规模，而分解所需的时间复杂度为Θ(1)，合并亦然，故其递推方程如下： $$T(n)=\{\begin{array}{ll}\Theta (1),& \text{若n = 1}\\ T(\frac{n}{2})+\Theta (1),& \text{其他}\end{array}$$ 由递推式可知二分查找的最坏情况运行时间为Θ(lgn)

2.3-6

  注意到2.1节中的过程INSERTION-SORT的第5～7行的while循环采用一种线性查找来（反向）扫描已排好序的子数组A［1…j-1］。我们可以使用二分查找（参见练习2.3-5）来把插入排序的最坏情况总运行时间改进到Θ（nlgn）吗？

  显然是不可以的，为此我们先贴出原来的插入排序：

INSERTION-SORT(A)

for j = 2 to A.length key = A[j] // Insert A[j] into the sorted sequence A[1 .. j - 1]. i = j - 1 while i > 0 and A[j] > key A[i + 1] = A[i] i = i - 1; A[i + 1] = key

  而二分查找的伪代码如下：

BINARYSEARCH(A, v)

l = 1 r = n while l < r q = (l + r) / 2 if A[q] < v l = q + 1 else if A[q] > v r = q - 1 else return q

  对其5 ~ 7行进行优化，则搜索到目标位置的时间确实减少，但仍需移动其后面的数据。

*2.3-7

  描述一个运行时间为Θ（nlgn）的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。

我们可以考虑先归并排序Θ（nlgn），然后再使用头部和尾部相向查找Θ（n），或者对每一个元素都进行一次二分查找Θ（nlgn）

CHECKSUM(A, x)

MERGE-SORT(A, 1, A.length) i = 1 j = A.length while i < j sum = A[i] + A[j] if(sum == v) return true else if(sum > v) j = j - 1 else i = i + 1 return false

2-1

  （在归并排序中对小数组采用插入排序） 虽然归并排序的最坏情况运行时间为Θ（nlgn），而插入排序的最坏情况运行时间为Θ（n²）,但是在插入排序的常量因子可能使得它在 n 较小时，在许多机器上实际运行得更快。因此，在归并排序中当子问题变得足够小时，采用插入排序来使递归的叶变粗是有意义的。考虑对归并排序的一种修改，其中使用插入排序来排序长度为 k 的 n / k 个子表，然后使用标准的合并机制来合并这些子表，这里 k 是一个待定的值。   a.证明：插入排序最坏情况可以在Θ（nk）时间内排序每个长度为k的n/k个子表。   b.表明在最坏情况下如何在Θ（nlg(n/k)）时间内合并这些子表。   c.假定修改后的算法的最坏情况运行时间为Θ（nk+nlg(n/k)），要使修改后的算法与标准的归并排序具有相同的运行时间，作为 n 的一个函数，借助Θ记号， k 的最大值是什么？   d.在实践中，我们应该如何选择 k ？

a.证明： Θ（n²）* (n / k) = Θ（nk） b.在最坏情况下，与归并排序相同，共需要分 lg(n/k) 层，每次合并使用 Θ（n）的时间，故而最坏情况下使用Θ（nlg(n/k)）时间内合并这些子表。 c.即使Θ（nk+nlg(n/k)） = Θ（nlgn），从而Θ（k+lg(n/k)） = Θ（lgn），故 k < lgn，最大值为lgn d.实践中k应该尽量选择为插入排序比合并排序快的最大的列表长度

2-2

  （冒泡排序的正确性） 冒泡排序是一种流行但低效的排序算法，它的作用是反复交换相邻的未按次序排列的元素。

BUBBLESORT(A)

for i = 1 to A.length - 1 for j = A.length downto i + 1 if A[j] < A[j - 1] exchange A[j] with A[j - 1]

  a.假设A’表示 BUBBLESORT(A) 的输出。为了证明 BUBBLESORT 正确，我们必须证明它将终止并且有： $$A^{\prime }[1]\le A^{\prime }[2]\le ...\le A^{\prime }[n]（2.3）$$   其中n = A.length。为了证明 BUBBLESORT 确实完成了排序，我们还需证明什么？   下面两部分将证明不等式（2.3）。   b.为第2 ~ 4行的 for循环精确地说明一个循环不变式，并证明该循环不变式成立。你的证明应该使用本章中给出的循环不变式证明的结构。   c.使用(b)部分证明的循环不变式的终止条件，为第 1 ~ 4 行的 for循环说明一个循环不变式，该不变式将使你能证明不等式（2.3）。你的证明应该使用本章中给出的循环不变式证明的结构。   d.冒泡排序的最坏情况运行时间是多少？与插入排序的运行时间相比，其性能如何？

a. A’中的元素全部来自A中的元素。

b.内循环的循环不变式：  每次内循环之前，都有 $$A[j]=min\{A[k]|j\le k\le n\}$$  并且子数组A[j…n]中的元素还是最初在A[j…n]中的元素。  证明：    初始化：在循环的第一次迭代之前，j = n，而A[n]未发生改变，循环不变式成立。    保持：假设此次迭代前循环不变式成立，根据循环不变式，A[j]是A[j…n]中最小的元素。第3 ~ 4行代码表示，如果A[j] < A[j - 1]，就交换A[j]和A[j-1]，显然经过迭代后下次迭代前，A[j - 1]是A[j - 1 . . n]中最小的元素。过程中最多仅发生比较与交换元素，且在迭代开始时，A[j . . n]中的元素最初都是在A[j . . n]中，所以在迭代开始时A[j - 1 . . n]中的元素最初都是在A[j - 1 . . n]中。   终止：循环终止时j = i。根据循环不变式，$$A[j]=min\{A[k]|j\le k\le n\}$$     并且A[i . . n]中的元素最初都在A[i . . n]中。

c.外循环的循环不变式：  每次外循环之前，前i - 1个数即A[1 . . i - 1]为A中最小有序的的 i - 1 个元素。  证明：    初始化：第一次迭代之前 i = 1。子数组A[1 . . i - 1]为空，循环不变式显然成立。    保持：假设此次迭代前循环不变式成立。根据循环不变式，前i - 1个数即A[1 . . i - 1]为A中最小有序的的 i - 1 个元素。此次迭代后，由(b)中的循环不变式，A[i]将是原A[i . . n]中最小的元素，即A[1 . . n]中第 i 小的数，故而循环不变式成立。    终止：循环终止时 i = n + 1。故根据循环不变式，A[1 . . i - 1]即A[1 . . n]中包含了A[1 . . n]全部元素且其有序。

d.最坏情况为所有数据都是从大到小排序的，这时候时间花费为Θ（n²）。最好情况是已经排好序的，仍然是Θ（n²），因为仍然需要双重循环。

2-3

  （霍纳(Horner)规则的正确性） 给定系数 a₀，a₁，… ，a_n 和 x 的值，代码片段

y = 0 for i = n downto 0 y = ai + x * y

  实现了用于求值多项式

$$P(x)=\sum _{k=0}^n{a}_k{x}^k=a_0+x(a_1+x(a_2+...+x(a_{n-1}+x{a}_n)...))$$   的霍纳规则。   a.借助Θ符号，实现霍纳规则的以上代码片段的运行时间是多少？   b.编写伪代码来实现朴素的多项式求值算法，该算法从头开始计算多项式的每个项。该算法的运行时间是多少？与霍纳算法相比，其性能如何？   c.考虑以下循环不变式：   在第 2 ~ 3 行for循环每次迭代的开始有 $$y=\sum _{k=0}^{n-(i+1)}{a}_{k+i+1}{x}^k$$   把没有项的和式解释为等于0。遵照本章中给出的循环不变式证明的结构，使用该循环不变式来证明终止时有 $$y=\sum _{k=0}^n{a}_k{x}^k$$   d.最后证明上面给出的代码片段将正确地求由系数a₀，a₁，…，a_n刻画的多项式的值。

a. Θ(n) b.伪代码如下：

NAIVE-POLYNOMIAL-EVALUATION(A, n)

y = A[0] for i = 1 to A.length y = y + x * A[i] x = x * x

Θ(n)；比霍纳规则性能略低。

c.与d.证明：    初始化：在循环的第一次迭代之前， i = n，原式为 $$y=\sum _{k=0}^{-1}{a}_{k+n+1}{x}^k=0$$        循环开始前y = 0显然成立，循环不变式成立。    保持：假设此次迭代前循环不变式成立。根据循环不变式，第 i 次迭代前循环不变式有$$y=\sum _{k=0}^{n-(i+2)}{a}_{k+i+2}{x}^k$$      此次迭代后，由代码片段 2 ~ 3 行，$$\begin{gathered} y=(\sum _{k=0}^{n-(i+2)}{a}_{k+i+2}{x}^k+1)\ast x+a_{i+1} \\ =\sum _{k=0}^{n-(i+2)}{a}_{k+i+2}{x}^{k+1}+a_{i+1} \\ =\sum _{k=1}^{n-(i+1)}{a}_{k+i+1}{x}^k+a_{i+1} \\ =\sum _{k=0}^{n-(i+1)}{a}_{k+i+1}{x}^k \end{gathered}$$       故而循环不变式$$y=\sum _{k=0}^{n-(i+1)}{a}_{k+i+1}{x}^k$$      成立。    终止：终止时i = -1，此时$$y=\sum _{k=0}^n{a}_k{x}^k$$      循环不变式成立。

2-4

  （逆序对） 假设A[1 . . n]是一个有 n 个不同数的数组。若 i < j 且 A[i] > A[j]，则对偶(i, j)称为A的一个逆序对(inversion)。   a.列出数组<2, 3, 8, 6, 1>的 5 个逆序对。   b.由集合{1,2, … , n}中的元素构成的什么数组具有最多的逆序对？它有多少逆序对？   c.插入排序的运行时间与输入数组中逆序对的数量之间是什么关系？证明你的回答。   d.给出一个确定在 n 个元素的任何排列中逆序对数量的算法，最坏情况需要 Θ(nlgn) 时间。（提示：修改归并排序。）

a. (2,1) (3,1) (8,1) (6,1),(8,6) b.数组从大到小有序排列时，逆序对最多，为n(n-1)/2个。 c.逆序对增加时，插入排序时间增加。   没有逆序对时，插入排序时间最少，为Θ(n)。   逆序对最多时，插入排序时间最多，为Θ(n²)。 d.伪代码如下：

COUNT-INVERSIONS(A, p, r)

inversions = 0 if p < r q = floor((p+r)/2) inversions = inversions + COUNT-INVERSIONS(A, p, q) inversions = inversions + COUNT-INVERSIONS(A, q+1, r) inversions = inversions + MERGE(A, p, q, r) return inversions

MERGE(A, p, q, r)

n1 = q - p + 1 n2 = r - p let L[1 .. n1 + 1] and R[1 .. n2 + 1] be new arrays for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = ∞ R[n2 + 1] = ∞ i = 1 j = 1 inversions = 0 counted = FALSE for k = p to r if counted == FALSE and R[j] < L[i] inversions = inversions + n1 - i + 1 counted = TRUE if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1 counted = FALSE return inversions