把时间花在有意义的地方

在研究算法的过程中,先从理论上给出一类算法在时间和空间上可以优化的上限,往往可以帮助我们认识哪些地方可以优化,哪些地方怎么优化是徒劳,从而将时间用在有价值的地方,而不是做没有意义的尝试。把时间花在有意义的事情上面,这正是我们研究算法的目的和意义所在。

决策树模型

基于比较来决策下一步的算法叫做CBA式算法(Comparison-Based Algorithm),CBA式的排序算法叫做比较排序算法。CBA式算法最坏情况的下界为$T(N) = O(log(TR(N)))​$,其中$N​$为数据输入量,$TR(N)​$为可能结果的总数。证明这一结论的一般方法是决策树模型,当然也可以使用信息论的方法。

对于给定规模的输入序列,决策树模型对元素之间初始的次序不做任何假设(或做所有假设),它会考虑每一种可能的排列,最终在适当的叶节点上列出对所有可能的输入执行的结果。不同的算法对应的决策树一般是不同的,因为决策树各分支的状态(序列)是依赖于算法如何做比较的。决策树叶节点上的状态是确定,而内部节点上的状态是不确定的,它有多种可能的状态,需要进一步比较加以确定,而比较会导致决策树发生分叉,产生两个子节点,子节点的确定性进一步增加直到完全确定。

比较排序算法的一次实际执行对应于从对应的决策树的根节点行进到决策树上的某个叶节点,其所需的比较次数为经过的路劲的长度。最坏情况下,算法的一次执行过程对应于从决策树的根节点行进到决策树上最深的叶节点。因此,一个比较排序算法在其最坏情况下所需的比较次数,就等于其决策树的高度。

对决策树的一个错误认知是,$N$个元素$N!$种排都应该出现在决策树的叶节点上,在这点上,包括《算法导论》的描述也是有问题的。事实上,用任何正确的确定型CBA排序算法对$N$个元素的集合的$N!$种排列进行排序,排序的结果肯定是唯一的,并且结果处于算法对应的决策树的叶节点上,只是不同的排列会走到不同的叶节点。具有$N$种可能排列的地方是根节点,根节点包含了太多的不确定性,它的次序是未知的,决不能说是一个排列。因为初始状态包含太多的不确定性,所以我们对其进行排序,就是要消除它的不确定性,从而得到一个确定的唯一的有序序列!在这个模型中,元素按编号(名字)访问,而不是按秩访问,因为排序是使得元素在秩上变得有序,所以便难免会打乱其在编号上的顺序。如果元素开始的编号都是相同的(一般地,人们会说,给定这样一个序列,${a_1, a_2,\cdots,a_N}$,这里面元素的顺序是不确定的,可以确定的是编号的次序),那么编号的$N!$种可能排列确实都应该出现在决策树的叶节点上。这$N!$种编号顺序,都对应着唯一的$N$个数的有序排列。这点与开始时刻编号有序,元素顺序不确定是倒过来的。

排序算法最坏情况的下界

上面已经说明,所有可能结果的总数,即决策树的叶节点数。决策树是一棵完全二叉树,因为每一次比较,都要从一棵树上分裂处两棵子树。现在我们来证明,具有$N$个叶节点的二叉树,其高度至少为$\lceil\log_2N\rceil​$。

这一证明可以间接地通过证明“高度为$h​$的二叉树最多有$2^h​$个叶节点”来完成。

证明:

直接计算法:

我们将具有两个儿子节点的节点叫做满节点(full node),将具有一个儿子节点的节点叫做单节点(single node)。可以证明,在一棵非空二叉树中,叶节点的个数为满节点的个数加$1$。

考虑一棵具有$N​$个节点的树,设$F​$为树中满节点个数,$L​$为叶节点个数,$S​$为具有一个儿子节点的节点个数。

因为每个节点有两个儿子指针,故$N$个节点总的儿子指针个数为$2N$。

除根节点外,树中每个节点都唯一地被一个儿子指针指向,故在$N$个节点的$2N$个儿子指针中,只有$N-1$个指向了有意义的地址,另外$N+1$个为空指针,由$L$个叶节点的$2L$个空指针和$S$个单节点的$S$个空指针组成。

根据以上阐述,$F,L,S$满足的关系为。
$$
\begin{cases}
2F + 2L + 2S = 2N \\
2L + S = N + 1
\end{cases}
$$
$\Rightarrow F+1 = L​$。

在一个叶节点上增加一个节点,叶节点的个数不变,相反,非叶节点的个数增加了。所以,节点个数固定后,只有在树中不含单节点的情况下,叶占比才能最大,叶个数才能达到最多。

此时,树中只有满节点和叶节点,满足$F+L = N​$. 由于$F = L - 1​$,所以$L=(N+1)/2​$。因为树中只有满节点和叶节点,所以$N​$必为奇数。

一棵高度为$h$的二叉树,具有最多$2^{h+1}-1$个节点,因此最多具有
$$
\frac{(2^{h+1}-1) + 1}{2} = 2^h
$$
个叶节点。

证毕。

归纳假设法:

如果$h=0$,则最多存在$2^0=1$个叶节点,满足。若$h$不为$0$,假设对如高度为$h$的树$T_1$,$T_1$具有最多的叶节点数$2^h$。现在,让我们我们给$T_1$增加$1$层,得到一棵$h+1$层的二叉树$T_2$。$T_2$有多少个叶节点,只需计算一下$T_1$中空指针的个数便知(这里的空指针只针对儿子指针而言)。这里不采取计算的策略,上面直接计算法证明中已经说明,只有在$T_1$中不含有单节点的情况下,$T_1$的叶节点的个数才能取到最大值$2^h$。所以$T_1$必是一棵完全二叉树(尽管不必完美),它的空指针全部位于叶节点上,空指针数目为$2 \cdot2^h = 2^{h+1}$,所以高度为$h+1$的二叉树$T_2$,其叶节点个数为$2^{h+1}$。

证毕。

排序算法的下界

$N$个元素一共有$N!$种不同的排列方式(假设这$N$个元素互异),这要求决策树具有$N!​$个叶节点;而每一次比较,决策树就会产生两个分支,所以排序算法的决策树一般是二叉树

对N个元素进行排序,需要的比较次数为$\lceil\log(N!)\rceil​$
$$
\begin{aligned}
\log(N!) &= log(N) + log(N-1) +\cdots+log(2)\\
&\geq log(N)+log(N-1)+\cdots+log(N/2)\\
&\geq \frac{N}{2}\log{\frac{N}{2}}\\
&= \frac{N}{2}\log{N}-\frac{N}{2}\\
&= \Omega(N\log{N})
\end{aligned}
$$
所以,所有基于比较的排序算法的时间复杂度的下界为$\Omega(N\log{N})$。具体说来,对$N$个元素的序列进行比较排序,无论采用什么算法,都至少需要$\lceil\log(N!)\rceil​$次比较才能完成。

这里便引出了题目中的问题——如何只使用7次比较对5个数进行排序,题目姑且将至命名为75排序。因为对5个元素进行排序至少需要$\lceil\log(5!)\rceil = 7$次比较,而且你不能对输入的序列怀有任何的假设,也就是说,你必须保证你的算法能对5个元素的120种排列均作出正确的排序,所以75排序问题是颇有一点难度的。

75排序问题

75排序问题,即仅用7次比较来对5个数排序的问题。这是使用最少比较次数进行排序的一次实践。
假设给定一个包含5个元素的任意序列:${a_0, a_1, a_2, a_3, a_4}$,下面我们来探讨一下如何使它变得有序。

  1. 开始的时候,每个元素都是等价的,因为比较在所难免,所以不妨先选两组(4个)数进行比较。
    为简单起见,我们让$a_0$和$a_1$比较并交换(如果需要的话),使得$a_0 < a_1$,并以$[a_0, a_1]$表示有序的序列${a_0, a_1}$,这将消耗一次比较的机会。同理我们将$a_2$和$a_3$比较并在必要时交换位置,从而得到${a_2, a_3}$的有序排列$[a_2, a_3]$。
    这时,我们消耗掉了两次比较的机会,得到${[a_0, a_1], [a_2, a_3]}$。

  2. 比较$a_1$和$a_3$并做一些操作使得前三个数有序。这样做的目的是后面要进行二分插入排序。
    比较$a_1$和$a_3$将有两种结果:

    • 如果$a_1 > a_3$,那么这时已知的最长的有序序列是$[a_2, a_3, a_1]$,我们将要进行一些操作使得有序序列变为$[a_0, a_1, a_2]$,以便接下来进行二分插入排序。解决方法便是,$a_0$和$a_2$交换,$a_1$和$a_3$交换,然后再将$a_0$和$a_1$交换。注意,这种情况下,我们已知$a_0 < a_1$,所以最后将$a_0$插入时只需将其插入前三个数,而无需考虑第四个数(可能是$a_1$和$a_4$)因为它必定大于$a_0$。
    • 否则,$a_1 \leq a_3$,但是我们并不知道$a_1$和$a_2$的大小关系,所以将$a_2$和$a_3$交换位置,以使得前三个数有序。这里,同上面的情况一样,$a_2$和$a_3$的大小关系是已知的,所以最后将$a_2$插入时只需考虑前三个数,而无需考虑第四个数。
  3. 第2步虽然进行了许多操作,实际上只进行了1次比较,所以到目前为之,我们一共使用了3次比较的机会,还剩4次比较的机会。
    接下来是将$a_4$插入前三个元素,因为前三个元素是有序的,所以我们使用二分插入的方法,每次插入需要2次比较。
    将最后一个数$a_4$插入有序序列$[a_0, a_1, a_2]$,得到有序序列$[a_0, a1, a_2, a_3]$,此时还剩下2次比较机会,由于第2步的缘故,我们已知最后一个数一定不是最大的,所以也将其二分插入到有序序列$[a_0, a_1, a_2]$中,从而得到有序序列$[a_0, a_1, a_2, a_3, a_4]$。 于是便完成了对5个数的任意排列的排序。

整个算法亦可用伪代码来描述,不过下面给出了C语言的描述,以及枚举5个数的全排列来对算法进行测试。

代码实现

///////////////////////////////
// running with Tinycc or Gcc//
///////////////////////////////
#include <stdio.h>

#define swap(a, b) ({ \
    typeof(a) tmp = a; a = b; b = tmp; })
#define cmpSwap(i, j) \
    if (A[i] > A[j]) swap(A[i], A[j])

// 将第5个元素以二分搜索的方式插入前三个元素中
#define insert_A4_into_A012()       \
{                                   \
    int pos;                        \
    if (A[4] < A[1]) {              \
        if (A[4] < A[0])            \
            pos = 0;                \
        else                        \
            pos = 1;                \
    }                               \
    else {                          \
        if (A[4] < A[2])            \
            pos = 2;                \
        else                        \
            pos = 3;                \
        }                           \
        int a4 = A[4];              \
    for (int i = 4; i > pos; --i)   \
        A[i] = A[i - 1];            \
    A[pos] = a4;                    \
}

// Sort 5 elements with only 7 comparisons
void sort5e7c(int *A)
{
    cmpSwap(0, 1);
    cmpSwap(2, 3);

    if (A[1] > A[3]) {
        int temp = A[0];
        A[0] = A[2];
        A[2] = A[1];
        A[1] = A[3];
        A[3] = temp;
    }
    else
        swap(A[2], A[3]);
    // insert A[4] into A[0, 1, 2], so that A[3] -> A[4]
    insert_A4_into_A012();
    // insert A[4] into A[0, 1, 2]
    insert_A4_into_A012();

}

有序性判断

int issorted(int *A, int len)
{
    for (int i = 0; i < len - 1; ++i)
        if (A[i] > A[i + 1])
            return 0;
    return 1;
}

测试算法的正确性

void full_permutation(int *A, int *B, void sort(int *), int begin, int end, int len);

void test_sort_algo(void sort(int *), int len)
{
    int A[len], B[len];
    for (int i = 0; i < len; ++i)
        A[i] = i + 1;
    // 对全排列进行测试
    full_permutation(A, B, sort, 0, len - 1, len);
}

int main()
{
    test_sort_algo(sort4e5c, 4);
    test_sort_algo(sort5e7c, 5);
    return 0;
}

枚举全排列

void full_permutation(int *A, int *B, void sort(int *), int begin, int end, int len)
{
    if (begin >= len) {
        memcpy(B, A, len * sizeof(int));
        sort(B);
        if (!issorted(B, len)) {
            printf("Fault order:\t");
        }
    }
    else {
        for (int i = begin; i <= end; ++i) {
            swap(A[begin], A[i]);
            full_permutation(A, B, sort, begin + 1, end, len);
            swap(A[begin], A[i]);
        }
    }
}

54排序问题

同75排序问题一样,也是使用最少的比较次数($\lceil\log(4!)\rceil = 5$)进行排序的实践,不过相对简单,下面只给出代码。

// 仅使用5次比较对4个元素进行排序
void sort4e5c(int *A)
{
    cmpSwap(0, 1);
    cmpSwap(2, 3);
    cmpSwap(0, 2);
    cmpSwap(1, 3);
    cmpSwap(1, 2);
}

这个代码是采用交换来实现的,其实如果我们使用归并排序来解决4个数的排序问题,也仅需要5次比较。