算法导论第 2 章：算法基础

发表于 分类于 Waline： 本文字数： 3.2k 阅读时长 ≈ 12 分钟

主要内容

本章介绍了一个贯穿全书的算法设计与分析的框架。正文中介绍了插入排序和归并排序两种排序算法，以它们为例，介绍了用循环不变式证明算法正确性的方法和分治法的思想。还介绍了如何分析算法的运行时间。

插入排序

本书介绍的第一个算法是插入排序算法。插入排序的工作机理和很多人打牌时，整理手中牌时的做法差不多。它的基本思想是，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。根据伪代码，给出如下的C语言实现：

1
2
3
4
5
6
7
8
9
10
11
void sort(int nums[], int n)
{
    for (int i = 1; i < n; i++) {
        int key = nums[i];
        int j;
        for (j = i - 1; key < nums[j] && j >= 0; j--) {
            nums[j+1] = nums[j];
        }
        nums[j+1] = key;
    }
}

利用循环不变式可以帮助我们理解算法的正确性。对于循环不变式，必须证明它的三个性质：

  1. 初始化：它在循环的第一轮迭代开始之前，应该是正确的
  2. 保持：如果在循环的某一次迭代之前它是正确的，那么，在下一次迭代之前，它也应该保持正确
  3. 终止：当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的

前两步和数学归纳法非常相似。

分析算法

本节以上面介绍的插入排序为例，展示如何分析算法的运行时间。用常数\(c_i\)表示计算机模型中基本操作所耗费的时间，推导出整个算法所需时间关于输入规模\(n\)的函数\(T(n)\)。算法分析一般只考察最坏情况运行时间，这是算法运行时间的上界。

当\(n\)很大时，\(T(n)\)的低阶项相对来说不太重要，高阶项的常系数也不重要。忽略它们后，只剩下最重要项的因子。例如，对于插入排序，只剩下\(n^2\)。我们记插入排序的最坏情况时间代价为\(\Theta(n^2)\)。

算法设计

本节介绍一种常用设计策略，叫做分治法（divide and conquer）。归并排序算法遵循分治模式，直观上其操作如下：

  • 分解：将\(n\)个元素分成各含\(n/2\)个元素的子序列
  • 合并：合并两个已排序的子序列以得到排序结果

当待排序的序列长度为1时，递归「开始回升」，在这种情况下不做任何工作，因为长度为1的每个序列已排好序。

为完成算法，需要一个完成合并的辅助过程。合并过程需要一个辅助数组。由于两个子序列是已经排序好的，所以合并步骤的时间复杂度仅为\(\Theta(n)\)。它的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void merge(int nums[], int aux[], int left, int mid, int right)
{
    for (int k = left; k <= right; k++) {
        aux[k] = nums[k];
    }

    int i = left;
    int j = mid + 1;
    for (int k = left; k <= right; k++) {
        if (i > mid) {
            nums[k] = aux[j++];
        } else if (j > right) {
            nums[k] = aux[i++];
        } else if (aux[j] < aux[i]) {
            nums[k] = aux[j++];
        } else {
            nums[k] = aux[i++];
        }
    }
}

下面便是递归调用过程的代码，merge_sort也是辅助过程，sort是最终的接口函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void merge_sort(int nums[], int aux[], int left, int right)
{
    if (left < right) {
        int mid = left + (right - left)/2;
        merge_sort(nums, aux, left, mid);       // 递归排序左边
        merge_sort(nums, aux, mid + 1, right);  // 递归排序右边
        merge(nums, aux, left, mid, right);     // 合并已排序好的两个数组
    }
}

void sort(int nums[], int n)
{
    // 开辟动态内存，作为参数传入
    int *aux = malloc(n * sizeof(int));
    if (aux != NULL) {
        merge_sort(nums, aux, 0, n - 1);
        free(aux);
    } else {
        printf("Error: malloc() failed!\n");
    }
}

当算法包含对其自身的递归调用时，要利用递归方程或递归式来描述其运行时间。对于上述的归并排序，算法分解成两个子问题加上一个合并过程，所以递归方程如下：

\[ T(n) = \begin{cases} c & \mbox{若} n=1 \\\\ 2T(n/2)+cn & \mbox{若} n>1 \end{cases} \]

根据上面的递归公式，可以计算出归并排序算法的时间复杂度为\(\Theta(n \lg n)\)。

习题解答

练习题

2.1-1 解答：如下：

1
2
3
4
5
6
31 41 59 26 41 58
31 41 59 26 41 58
31 41 59 26 41 58
26 31 41 59 41 58
26 31 41 41 59 58
26 31 41 41 58 59

2.1-2 解答：将大于号改为小于号即可。

2.1-3 解答：用代码更简单。注意CLRS的伪代码下标从1开始，主流编程语言下标从0开始。线性查找算法的实现如下：

1
2
3
4
5
6
7
8
9
int LinearFind(const vector<int> &A, int v)
{
    for (auto i = 0; i < A.size(); i++) {
        if (v == A[i]) {
            return i;
        }
    }
    return -1;
}

循环不变量为：\(A[1..i-1]\)不包含\(v\)。根据该循环不变量证明算法正确性如下：

  • 初始化：当\(i=1\)时，\(A[1..i-1]\)为空，不包含\(v\)，这表明第一次循环迭代之前循环不变式成立
  • 保持：当下标为\(i\)的值不等于\(v\)时，则\(A[1..i]\)不包含\(v\)；当下标为\(i\)的值等于\(v\)时，循环立即结束。那么在下一次迭代之前，循环不变式依然成立
  • 终止：循环终止的条件是找到\(v\)后函数返回或\(i>A.length\)。第一种情况下，函数找到\(v\)，正确；第二种情况下有\(i=A.length+1\)，循环不变式为\(A[1..n]\)，不包含\(v\)，返回\(NIL\)，算法正确。

2.1-4 解答：代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> AddBinary(const vector<int> &A, const vector<int> &B)
{
    vector<int> C(A.size()+1, 0);
    int carry = 0;
    for (auto i = 0; i < A.size(); i++) {
        C[i] = (A[i] + B[i] + carry) % 2;
        carry = (A[i] + B[i] + carry) / 2;
    }
    C[A.size()] = carry;

    return C;
}

2.2-1 解答：\(\Theta(n^3)\)

2.2-2 解答：选择排序算法的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sort(int A[], int n)
{
    for (int i = 0; i < n; i++) {
        int m = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[m]) {
                m = j;
            }
        }
        if (m != i) {
            int tmp = A[i];
            A[i] = A[m];
            A[m] = tmp;
        }
    }
}

该算法维持的循环不变量是：\(A[1:i-1]\)是排好序的。因为前\(n-1\)个元素有序之后，第\(n\)个即为最大的元素，排在末尾是正确的位置，无需处理。最好情况是\(\Theta(n)\)，最坏情况是\(\Theta(n^2)\)。

2.2-3 解答：平均需要检查\(n/2\)个元素，最坏需检查\(n\)个元素。平均情况和最坏情况运行时间均为\(\Theta(n)\)。

2.2-4 解答：将输入设置为算法具有最好运行时间的情况。

2.3-1 解答：如下图：

1
2
3
4
5
6
7
       03 09 26 38 41 49 52 57
         /                 \
   03 26 41 52         09 38 49 57
    /       \           /        \
 03 41     26 52     38 57     09 49
 /   \     /   \     /   \     /   \
03   41   52   26   38   57   09   49

2.3-2 解答：我上面列出的代码就是这么实现的。

2.3-3 解答：令\(n = 2^k\)，按照数学归纳法的步骤，证明（1）\(k = 1\)时，成立；（2）\(k = a\)时公式成立，\(k = a+1\)时公式也成立。详细过程略。

2.3-4 解答：递归公式如下：

\[ T(n) = \begin{cases} \Theta(1) & \mbox{若} n=1 \\\\ T(n-1)+\Theta(n) & \mbox{若} n>1 \end{cases} \]

2.3-5 解答：二分查找的迭代实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int BinarySearch(int nums[], int n, int key)
{
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int mid = left + (right-left)/2;
        if (nums[mid] < key) {
            left = mid + 1;
        } else if (nums[mid] > key) {
            right = mid - 1;
        } else {
            return mid;
        }
    }

    return -1;
}

递归实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int search(int nums[], int left, int right, int key)
{
    if (left <= right) {
        int mid = left + (right-left)/2;
        if (nums[mid] < key) {
            return search(nums, mid+1, right, key);
        } else if (nums[mid] > key) {
            return search(nums, left, mid-1, key);
        } else {
            return mid;
        }
    }

    return -1;
}

int BinarySearch(int nums[], int n, int key)
{
    return search(nums, 0, n-1, key);
}

递归表达式为：\(T(n) = 2T(n/2) + c\)，所以最坏情况运行时间为\(\Theta(\lg n)\)。

2.3-6 解答：不能。找到插入的位置的时间可以做到\(\Theta(\lg n)\)，但是移动元素依然需要\(\Theta(n)\)。

2.3-7 解答：先将集合\(S\)用\(\Theta(n \lg n)\)的时间排序；然后遍历序列，对每个元素\(S[i]\)，利用二分查找算法搜索序列中是否包含\(x - S[i]\)，耗费时间\(\Theta(n \lg n)\)。整体的运行时间即为\(\Theta(n \lg n)\)。

思考题

2-1 （在归并排序中对小数组采用插入排序）当\(n\)较小时，插入排序比归并排序运行更快。考虑到对合并排序做这样的修改，对\(n/k\)个长度为\(k\)的子列表进行排序，然后再用标准的合并机制将它们合并起来，此处\(k\)是个待定的值。问题如下：

  1. 证明在最坏情况下，\(n/k\)个子列表（每一个子列表的长度为\(k\)）可以用插入排序在\(\Theta(nk)\)时间内完成排序。 解答：排序长度为\(k\)的子列表耗时\(\Theta(k^2)\)，一共有\(n/k\)个子表，两式相乘得到\(\Theta(nk)\)。
  2. 表明在最坏情况下如何在\(\Theta(n \lg (n/k))\)时间内合并这些子表。 解答：将长度为\(k\)的子列表利用前面的合并算法两两合并，然后重复两两合并的操作，直到得到一个总表。一共有\(\lg (n/k)\)层，每层耗时\(\Theta(n)\)，两式相乘得到\(\Theta(n \lg (n/k))\)。
  3. 假定修改后的算法的最坏情况运行时间为\(\Theta(nk + n \lg (n/k))\)，要使修改后的算法与标准的归并排序具有相同的运行时间，\(k\)的最大值是什么？借助\(\Theta\)记号，用\(n\)的一个函数来表示。 解答：\(k\)的最大值为\(\Theta(\lg n)\)。
  4. 在实践中，该如何选择\(k\)？ 解答：选择的\(k\)值应该使得插入排序比归并排序运行速度快。

2-2 （冒泡排序算法的正确性） 冒泡排序是一种流行但低效的排序算法，请证明它的正确性，并分析它的运行时间。下面是它的实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
void sort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = n - 1; j > i; j--) {
            if (A[j] < A[j-1]) {
                int tmp = A[j];
                A[j] = A[j-1];
                A[j-1] = A[j];
            }
        }
    }
}

解答：冒泡排序算法的正确性证明，略。它的运行时间为\(\Theta(n^2)\)。由于内循环的交换操作比较耗时，冒泡排序比插入排序算法要慢。

2-3 （Horner规则的正确性） Horner规则的多项式如下：

\[ 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)...)) \]

代码实现如下：

1
2
3
4
5
6
7
8
9
10
// 数组a[]的大小应该为n + 1
int horner(int a[], int n, int x)
{
    int y = 0;
    for (i = n; i >= 0; i--) {
        y = a[i] + x * y;
    }

    return y;
}

问题如下：

  1. 借助\(\Theta\)符号，实现Horner规则的以上代码片段的运行时间是多少？ 解答：\(\Theta(n)\)。
  2. 朴素的多项式求值算法从头开始计算多项式的每个项，算法的运行时间是多少？ 解答：\(\Theta(n^2)\)，性能比Horner规则差。
  3. 考虑循环不变式：在循环每次迭代的开始有\(y = \sum_{k=0}^{n-(i+1)} a_{k+i+1}x^k\)，不包含任何项的和视为等于0，证明在终止时有\(y = \sum_{k=0}^n a_k x^k\) 解答：未完成。

2-4 （逆序对） 对数组\(A[1..n]\)，若\(i < j\)且\(A[i] > A[j]\)，则对偶\((i, j)\)称为\(A\)的一个逆序对。问题如下：

  1. 列出数组\([2, 3, 8, 6, 1]\)的5个逆序对。 解答：\((2, 1)\)，\((3, 1)\)，\((8, 6)\)，\((8, 1)\)，\((6, 1)\)
  2. 由集合\(1, 2, ..., n\)中的元素组成的什么数组具有最多的逆序对？它有多少逆序对？ 解答：倒序数组\([n, ..., 2, 1]\)有最多的逆序对，有\(n(n-1)/2\)对。
  3. 插入排序的运行时间与输入数组中逆序对的数量之间有什么关系？证明你的回答。 解答：逆序对的数量越多，插入排序的运行时间越长。因为内循环中移动元素的次数会增多。
  4. 给出一个算法，它能用\(\Theta(n \lg n)\)的最坏情况运行时间，确定\(n\)个元素的任何排列中逆序对的数量。（提示：修改合并排序） 解答：总的逆序数量等于两个子序列逆序数量之和加上跨越两个子序列的逆序的数量。原来的排序过程保持不变，需增加对逆序进行计数的操作。由于子序列是排序过的，计数操作的运行时间也是\(\Theta(n)\)，所以算法总的运行时间为\(\Theta(n \lg n)\)。