算法基础─算法导论(1)

2015年09月05日 02:04

1. 从插入排序说起

插入排序（insert-sort） 在我们的日常生活中其实使用得非常广泛。比如我们在玩扑克时，右手（当然，不考虑左撇子）不断从桌上拿起一张扑克，按大小插入到左手的扑克序列的相应位置中。在结束时，左手的扑克是排好序的。按照这种思想，我们便总结出了所谓的 插入排序。

下面给出 插入排序 的 Java 实现代码：

public static void insertSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int j = i - 1;
        // curr 表示要插入的扑克
        int curr = a[i];
        // 要插入的扑克从左手的扑克序列最右端不断向左移动
        // 直到到了尽头或者要插入的扑克比左手某一扑克大时，就停止移动
        while (j > -1 && curr < a[j]) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = curr;
    }
}

2. 循环不变式

循环不变式是用来帮助我们理解（或证明）算法的正确性的有力工具。

所谓循环不变式，顾名思义就是在循环的每轮结束时，一个始终成立的式子（或结论）。例如在以上程序中，每轮循环结束（外层for循环）时，a[0 ~ i]（表示a数组的0 ~ i位）都是排好序的，我们把a[0 ~ i]的这一性质形式地表示为一个 循环不变式。

运用 循环不变式，要理解（或证明）算法的正确性，我们需要三个步骤：

1. 初始化（Initialization） 循环第一次迭代之前，它为true；
2. 保持（Maintenance） 如果循环迭代式某次迭代之前它为true，那么下次迭代之前它也为true；
3. 终止（Termination） 在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的；

以上面的 插入排序 为例，给出该算法的证明：

1. 初始化 在第一次迭代之前，子数组只有一位a[0]，显然成立；
2. 保持 假设在第i次迭代之前，不变式成立，即子数组a[0 ~ i-1]是排好序的；在进行第i次迭代时，根据算法，a[i]从子数组a[0 ~ i-1]的最右端不断向左移动，直到找到自己合适的位置，此时子数组由a[0 ~ i-1]扩充为a[0 ~ i]。因此在进行第i+1次迭代之前，子数组a[0 ~ i]也是排好序的。
3. 终止 外层for循环终止的条件是，i = a.length - 1。根据保持性，此时子数组扩充为a[0 ~ a.length-1]，且是排好序的。

3. 算法分析

算法分析 主要是分析算法的在时间和空间上的复杂度，这两点很重要，它们是衡量一个算法好坏的重要因素。算法分析 的前提是算法是正确的，否则它是没有意义的。

由于算法的实现与运行环境也会影响它的时间与空间的复杂度，因此我们假定一种通用的单处理器计算模型——随机访问机（random-access machine，RAM）来作为实现技术的模型。在该模型中，一些常用的计算机指令，包括算术指令（加、减、乘、除、取余、向上取整、向下取整）、数据移动指令（装入、储存、复制）和控制指令（条件与无条件转移、子程序调用与返回），它们执行所需的时间为常量。基于以上假设，我们就可以只在算法的简单层面上去衡量它时间与空间的复杂度。

还是以 插入排序 为例：

//(c, n)，第一个参数表示该步执行一次的时间，第二个参数表示该步执行的次数。
for (int i = 1; i < a.length; i++) { // (c1, n)
    int j = i - 1; //(c2, n-1)
    int curr = a[i]; // (c3, n-1)
    while (j > -1 && curr < a[j]) { // (c4, t2+t3+...+tn)
        a[j + 1] = a[j];// (c5, (t2-1)+(t3-1)+...+(tn-1))
        j--;// (c6, (t2-1)+(t3-1)+...+(tn-1))
    }
    a[j + 1] = curr;// (c7, n-1)
}

算法的时间复杂度在：

• 最佳情况： T(n) =c1 * n + c2 * (n - 1) + c3 * (n - 1) + c4 * (n - 1) + c7 * (n - 1)= (c1 + c2 + c3 + c4 + c7) * n – (c2 + c3 + c4 + c7)

• 最坏情况： T(n) = c1 * n + (c2 + c3 + c7) * (n - 1) + c4 * [n(1 + n) / 2 - 1] + (c5 + c6) * [n(1 + n) / 2] = (c4 / 2 + c5 / 2 + c6 / 2) * n^2 + (c1 + c2 + c3 + c7 - c4 / 2 - c5 / 2 - c6 / 2) * n – (c2 + c3 + c7 + c4)

我们可以把T(n)表示为an^2 + bn + c，它是n的二次函数。

做更近一步的简化抽象，我们真正感兴趣的是运算时间的增长率（增长量级）。因此忽略低阶项和最高阶项的常系数。记 插入排序 的最佳情况运行时间为：θ(n)，最坏情况运行时间为：θ(n²)。

对于 插入排序 ，我们更应该考虑的是最坏情况，因为：

1. 最坏情况给出了一个上界，可以确保该算法不会超过某一时间；
2. 最坏情况往往经常出现；
3. “平均情况”和最坏情况大致一样差。

4. 算法设计

算法设计是对算法设计过程的总结，是指导我们设计一个新的算法的思想。

以 插入排序 为例，它实际上是采用了一种叫做增量的方法，即将a[i]插入子数组a[0 ~ i-1]中，子数组增长为：a[0 ~ i]。

下面我们再介绍一种叫做 分治法（Divide and Conquer） 的设计方法，它的主要思想是：

将原问题分解为几个规模较小的但类似于原问题的子问题，递归的解决这些子问题，然后合并这些子问题的解来建立原问题的解。

我们把运用 分治法 解决排序问题的算法取名为归并排序（merge-sort），其大致步骤如下：

1. 分解： 将待排序的具有n个元素的序列分成2个具有n / 2个元素的子序列；
2. 解决： 使用归并排序递归的解决2个子序列；
3. 合并： 合并已排序的2个子序列得到答案；

/**
 * 将a[pr]排序
 * @param a
 * @param p
 * @param r
 */
public static void mergeSort(int[] a, int p, int r) {
    if (p < r) {
        int q = (r + p) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

/**
 * 合并2个已排序的序列(a[p  q]和a[q+1  r])
 * @param a
 * @param p q >= p
 * @param q
 * @param r
 */
public static void merge(int[] a, int p, int q, int r) {
    int[] a1 = new int[q - p + 2];
    int[] a2 = new int[r - q + 1];
    for (int i = 0; i < a1.length - 1; i++) {
        a1[i] = a[p + i];
    }
    a1[a1.length - 1] = Integer.MAX_VALUE;
    for (int i = 0; i < a2.length - 1; i++) {
        a2[i] = a[q + i + 1];
    }
    a2[a2.length - 1] = Integer.MAX_VALUE;
    int m = 0, n = 0;
    for (int i = p; i < r + 1; i++) {
        if (a1[m] < a2[n]) {
            a[i] = a1[m];
            m++;
        } else {
            a[i] = a2[n];
            n++;
        }
    }
}

下面我们简单分析一下 分治法：

设T(n)为规模为n的问题运用分治法所需的运行时间。若问题规模足够小，如对于某个常量c，n <= c，则直接求解需要常量时间，记为：θ(1)；否则，把问题分解成a个子问题，每个子问题的规模是原来的1 / b，则T(n) = a * T(n / b)，如果分解为子问题所需时间为D(n) （可记为：θ(1)），合并子问题所需的时间为C(n)（可记为：θ(n)），那么T(n)递归式为：

$T(n) = \begin{cases} \Theta(1) & n \leq c\\ aT(n / b) + D(n) + C(n) & n > c \end{cases}$

特别的，对于 归并排序 有：

$T(n) = \begin{cases} \Theta(1) & n = 1 \\ 2T(n / 2) + \Theta(1) & n > 1 \end{cases}$

可以求得$T(n) = c * n * lg n + c * n$，记为：$\Theta(n * lg n)$。

可见当n较大时，在最坏情况下，归并排序 优于 插入排序。