排序算法、时间复杂度与信息熵

在这篇文章里，我们从信息论的角度证明了，基于比较的排序算法需要的比较次数（在最坏情况下）至少为log2(n!)，而log(n!)=Θ(nlogn)，这给出了比较排序的一个下界。但那里我们讨论的只是最理想的情况。一个事件本身所含的信息量是有大小之分的。看到这篇文章(http://users.aims.ac.za/~mackay/sorting/sorting.html)之后，我的思路突然开阔了不少：信息论是非常强大的，它并不只是一个用来分析理论最优决策的工具。从信息论的角度来分析算法效率是一件很有趣的事，它给我们分析排序算法带来了一种新的思路。

假如你手里有一枚硬币。你希望通过抛掷硬币的方法来决定今天晚上干什么，正面上网反面看电影。投掷硬币所产生的结果将给你带来一些“信息”，这些信息的多少就叫做“信息量”。如果这个硬币是“公正”的，正面和反面出现的概率一样，那么投掷硬币后不管结果咋样，你都获得了1 bit的信息量。如果你事先就已经知道这个硬币并不是均匀的，比如出现正面的概率本来就要大得多，这时我们就说事件结果的不确定性比刚才更小。如果投掷出来你发现硬币果然是正面朝上，这时你得到的信息量就相对更小（小于1 bit）；反之如果投掷出来居然反面朝上了，那你就得到了一个相对较大的信息量（大于1 bit）。但平均下来，我们得到的信息量是小于1 bit的，因为前者发生的可能性毕竟要大一些。最极端的情况就是，这是一枚被捣了鬼的魔术硬币，你怎么投都是正面。此时，你投了硬币等于没投，反正结果都是正面朝上，你得到的信息量永远为0。

这个理论是很符合生活实际的。昨天晚上我出去吃饭时，坐在我后面的那个人是男的还是女的？这种问题就比较有价值，因为大家都猜不到答案究竟是什么；但要问我昨天跟谁一起出去上自习去了，问题的答案所含的信息量就变小了，因为大家都知道如果我破天荒地跑去自习了的话多半是有MM陪着一起去的。如果有网友问我是男的还是女的，那就更不可思议了，因为我不但多次在这个Blog里提到我一直想找一个合适的MM，还在AboutMe里面发了我的照片。如果某人刚操完一个MM，突然扭过头去问“对了，你是男的还是女的呀”，那这个人绝对是一个不折不扣的大傻B，因为这个问题所能带来的信息量几乎为0。

总之，当每种结果出现的概率都相等，事件的不确定性达到最大，其结果最难预测时，事件的发生将会给我们带来最大的信息量。我们把一个事件的不确定程度叫做“熵”，熵越大表明这个事件的结果越难以预测，同时事件的发生将给我们带来越多的信息。如果在排序算法里每次比较的熵都是最大的，理论上来说这种（基于比较的）排序算法就应当是最优的。但我们一会儿将看到，我们已知的排序算法总是不完美的，每种算法都会或多或少地存在一些价值明显不大的比较。

首先我们来看三种经典的平方复杂度算法。它们的效率并不高，原因就在于算法过程中会出现越来越多概率严重不均的比较。随着冒泡排序的进行，整个序列将变得越来越有序，位置颠倒的泡泡将越来越少；选择排序的每一趟选择中，你都会不断得到越来越大的数，同时在以后的比较中找到更大的数的概率也越来越低；在插入排序中，你总是把新的数与已经排好的数按从大到小的顺序依次进行比较，可以想到新的数一开始就比前面所有的数中最大的那个还大的概率是相当小的。受此启发，我们可以很自然地想到一个插入排序的改进：处理一个新的数时，为何不一开始就与前面处理过的数中的中位数进行比较？这种比较的熵显然更大，能获取的信息量要大得多，明显更有价值一些。这就是插入排序的二分查找改进。

下面我们再来看一看几种O(nlogn)的排序算法。在快速排序算法中，比较的信息熵不会因为排序算法的进行而渐渐减小，这就是快速排序比上面几个排序算法更优秀的根本原因。仔细回顾快速排序算法的过程，我们立即看出，每次比较的两种结果出现的概率完全由这一趟划分过程所选择的基准关键字决定：选择的基准关键字刚好是当前处理的数字集合的中位数，则比较结果的不确定性达到最大；如果选择的基准关键字过大或过小，都会出现比较产生的结果不均等的情况，这使得每次比较平均带来的信息量大大减少。因此，快速排序算法是很看人品的：如果基准选的好，算法完全有可能达到理论上的最优；如果基准选的不好，复杂度很容易退化到O(n^2)。

堆排序所需要的比较次数更多，因为在堆的删除操作中有一种明显不平衡的比较。在删除操作中，我们把根节点用整个堆的最末一个节点来代替，然后不断下沉直到它的儿子都比它大。判断它的两个儿子是否比它大，其信息熵是相当小的，因为这个节点本身就来自堆的底部，除非这个节点已经沉到很底下了，否则儿子比它大的概率是很小的。因此，我们想到了一个堆排序的优化：反正堆建好了以后不需要再插入新元素了，为何不舍弃堆的完全二叉树性质？我们可以直接把根元素改成无穷大，让它沉到底，不用再考虑儿子比它大的问题了，也不再顾及堆的形状。这样的话，堆排序是否就完美了呢？仔细想想你会发现，改进之后的比较操作仍然是不对称的。这种不对称主要来自两个方面：左子树和右子树的节点个数不同，以及被删除的根节点原先是来自左子树还是右子树。比方说，根节点原本就是从右子树提上来的，现在删除了根节点后，左子树的最小值比右子树的最小值更小的概率就偏大一些；此时万一右子树节点本来就比左边少，这样的话这个比较的熵就更小了。

最后看一下归并排序。在有序队列的合并操作中，绝大多数情况下的比较操作都是比较平衡的。左边一半中的最小值和右边一半中的最小值进行比较，结果显然是等概率的。当然，随后将发生其中一边的最小值与另一边的次小值进行比较，这时的比较操作略微有了一些不平衡，并存在较小的可能使得比较操作变得更加不平衡（最小值与第三小的值相比）。有趣的是，比较越是不平衡，重新归于平衡的概率就越大，就好像归并排序中的信息熵会自动调整一样。这就是归并排序比平方复杂度的排序算法效率更高的原因。当然，完全有可能出现这样的情况：右边的数奇小无比，左边的最小值比右边的所有值都大。结果最后右边的队列都处理完了左边还没开始取数，此时合并操作提前结束，所花费的比较次数出人意料地少。从信息熵的角度来看，这种“比较提前结束”的现象是非常自然的：这种情况毕竟是“出人意料”的，事实越出人意料，获得的信息量就越大，因此算法就提前结束了。但这种情况毕竟是相当罕见的，平均情况下每次比较的信息量仍然不足1 bit。

最后，为什么线性排序的算法可以达到O(n)的复杂度？这是因为，线性排序算法并不是基于比较的。一次比较事件（假设没有相等的情况）所能产生的信息量最多1 bit，而一次Hash分类可以获得的信息量远远超过了1 bit，因为它可以一次确定出n种等概率的可能情况。