《算法导论》插入排序和归并排序的算法分析

2022-06-09 本文已影响0人 Sun东辉

首先，需要介绍一个概念

循环不变式

作用：主要用来帮助我们理解算法的正确性。

对于循环不变式，必须证明它的三个性质：

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

插入排序算法分析

机理

使用增量方法，在排好子数组 A[1…j-1]后，将元素 A[j] 插入，形成排好序的子数组 A[1…j]。

特点

实现简单，运行并不需要额外的存储空间，空间复杂度为 O(1)，在数据规模较小时，表现较好。

分析

伪代码实现如下（其中， $t_j$ 表示对值 j 执行 while 循环测试的次数）：

该算法的运行时间 T(n) 是执行每条语句的运行时间之和。即

$T(n)\;=\;c_1n+c_2(n-1)+c_4(n-1)+c_5\sum_{j=2}^nt_j+c_6\sum_{j=2}^n(t_j-1)+c_7\sum_{j=2}^n(t_j-1)+c_8(n-1)$

可以看出，该算法的运行时间取决于输入值的情况，在最佳情况下（输入值已经是升序排序的），第 5 行总是存在 A[i]≤key，于是最佳运行时间的计算如下：

$T(n)\;=\;c_1n+c_2(n-1)+c_4(n-1)+c_5(n-1)+c_8(n-1)=(c_1+c_2+c_4+c_5+c_8)n-(c_2+c_4+c_5+c_8)$

运行时间可以表示为

$an+b$

常量 a 和 b 依赖于语句的代价 $c_i$ ，因此，它是 n 的一个线性函数。

如果输入数组是按照逆序排序的，那么就会出现最坏的情况，此时，每个元素 A[j] 都会与整个已排序的子数组 A[1…j-1] 中的每一个元素进行比较，此时：

$\sum_{j=2}^nt_j=\frac{n(n+1)}2-1$

和

$\overset n{\underset{j=2}{\sum(}}t_j-1)=\frac{n(n-1)}2$

此时，该算法的运行时间为：

$T(n)\;=\;c_1n+c_2(n-1)+c_4(n-1)+c_5(\frac{n(n+1)}2-1)+c_6(\frac{n(n-1)}2)+c_7(\frac{n(n-1)}2)+c_8(n-1)=(\frac{c_5}2+\frac{c_6}2+\frac{c_7}2)n^2+(c_1+c_2+c_4+\frac{c_5}2-\frac{c_6}2-\frac{c_7}2+c_8)n-(c_2+c_4+c_5+c_8)$

我们可以把最坏情况运行时间表示为

$an^2+bm+c$

其中常量 a、b 和 c 又依赖于语句代价 $c_i$ ，因此，它是 n 的二次函数。

算法的正确性证明（使用循环不变式来证明算法的正确性）

初始化：首先，先证明在第一轮迭代开始之前，循环不变式是成立的。此时，j=2，而子数组为 A[1…j-1]，这样，它只包含一个元素 A[1]，实际上就是最初在 A[1] 中的那个元素。这个子数组是已排序的（这一点是显然的），这样就证明了循环不变式在循环的第一轮迭代开始之前是成立的。
保持：接下来，我们来考虑第二个性质：证明每一轮循环都能使循环不变式保持成立。从非形式化的意义上来看，在外层 for 循环的循环体中，要将 A[j-1]、A[j-2]、A[j-3]等元素向右移一个位置，直到找到 A[j] 的适当位置时为止，这时将 A[j] 的值插入。如果要更形式化地证明第二个性质成立的话，就需要陈述并证明对内层 while 循环也有一个循环不变式成立。但是，此处我们更倾向于暂时不陷于过于形式化的细节之中，而是依赖于非形式化的分析，来证明第二个性质对于外层循环是成立的。
终止：最后，分析一下循环结束时的情况。对于插入排序来说，当 j 大于 n 时（即当 j=n+1 时），外层 for 循环结束。在循环不变式中，将 j 替换为 n+1，就有子数组 A[1..n]包含了原先 A[1..n]中的元素，但现在已排好序了。但是，子数组 A[1..n]其实就是整个数组！因此，整个数组就排好序了，这意味着算法是正确的。

归并排序(分治法)算法分析

机理

分解：分解原问题为若干子问题（在归并排序中采用二分法），这些子问题是原问题的规模较小的实例。
解决：解决这些子问题，递归地求解各个子问题，如果子问题的规模足够小，则直接求解（在归并排序中，当待排序的序列长度为 1 时，递归“开始回升”）。
合并：将子问题的结果合并成原问题的解。
归并排序的时间复杂度是非常稳定的，不管是最好情况、最坏情况、还是平均情况，时间复杂度都是O(nlogn)。

分析

伪代码实现如下：

    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)

    MERGE(A,p,q,r)
    n1 = q - p + 1 # 计算子数组 A[p..q] 的长度 n1
    n2 = r - q     # 计算子数组 A[q+1...r] 的长度 n2
    let L[1...n1+1] and R[1...n2+1] be new arrays # 创建数组 L 和 R，长度各为 n1+1 和 n2+1
    for i = 1 to n1 # 将子数组 A[p...q]复制到 L[1...n1]中去
        L[i] = A[p+i-1]
    for j = 1 to n2 # 将子数组 A[q+1...r]复制到 R[1...n2]中去
        R[j] = A[q+j]
    L[n1+1] = ∞ # 将哨兵置于数组 L 的末尾
    R[n2+1] = ∞ # 将哨兵置于数组 R 的末尾
    i = 1  # 从这一行开始到结束，通过维护循环不变式，执行了 r-p+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

该算法的运行时间为：

$T(n)\;=\left\{\begin{array}{l}\Theta(1)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;n\;\leq\;C\\aT(n/b)+D(n)+C(n)\;\;\;\;\;\;n>C\end{array}\;\;\right.$

其中，常量 C 为常量，若 C≥n，则直接求解，其求解的时间为常量时间 $\Theta(1)$ ，若 C<n，则将问题分解成 a 个子问题，每个子问题的规模是原问题的 1/b（对于归并排序，a 和 b 都等于 2），求解规模为 n/b 的子问题的时间为 T(n/b)，分解问题成子问题的时间为 D(n)，合并子问题的解的时间为 C(n)。

为了更直观地理解归并算法的的解，我们可以把递归式重写为：

$T(n)\;=\left\{\begin{array}{l}c\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;若\;n\;=\;1\\2T(n/2)+cn\;\;\;\;\;\;若\;n>1\end{array}\;\;\right.$

其中常量 c 代表求解规模为 1 的问题所需的时间以及在分解步骤与合并步骤处理每个数组元素所需要的时间。

出于方便性考虑，假设 n 是 2 的整数幂，如图所示，cn 项是树根（即顶层递归的代价），根的两棵子树是两个更小一点儿的递归式 T(n/2)，T(n/2) =2T(n/4)+cn/2，依此类推，继续递归，直到问题的规模降到了 1，这时每个问题的代价为 c。

接着，我们把穿过这棵树的每层的所有代价相加，顶层具有的代价为 cn，下一层具有的总代价 c(n/2)+c(n/2) = cn，下一层的下一层具有的总代价为 c(n/4)+c(n/4)+c(n/4)+c(n/4) = cn，第 i 层具有的总代价为 $2^ic(n/2^i) = cn$ ，底层具有 n 个节点，每个节点贡献代价为 c，该层的总代价为 cn。

递归树的根为 cn，每次进行二分，直至底层为 n 个 c，可以很容易的得出这棵树的高度为 lgn+1，为了计算递归式的总代价，我们只需要将各层的代价加起来，即总代价为

$cn(lgn+1) = cnlgn+cn$ ，忽略低阶项和常量 c，可以得出复杂度为 $\Theta(nlgn)$ 。

算法的正确性证明

初始化：在 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 个最小的元素。增加 k 的值（在 for 循环中更新计数器变量的值时）和 i 的值，会为下一轮迭代重新建立循环不变式的值。如果这次有 L[i]≥R[j]，也会执行适当的操作，使得循环不变式保持成立。
终止：在终止时，k=r+1。根据循环不变式，子数组 A[p..k-1]（此时即 A[p..r]）包含了 L[1.. $n_1$ +1]和 R[1.. $n_2+1$ ]中 k-p=r-p+1 个最小元素，并且是已排好序的。数组 L 和 R 合起来，包含了 $n_1+n_2+2=r-p+3$ 个元素。除了两个最大元素外，其余所有元素都已被复制回数组 A 中，这两个最大元素都是哨兵。