信息熵在排序算法中的应用信息熵在排序算法中的应用.ppt

* 应用信息熵研究排序算法效率 王羽笙 * 信息熵和排序的关系 序列的信息熵 几种排序算法的分析 利用信息熵原理寻找高效的排序方法 结论 * 信息熵和排序的关系 信息熵：一个事件的 不确定程度 排序：使序列从 无序 到有序的过程 可以用信息熵来描述序列的无序程度 进而研究排序算法的效率 * 序列的信息熵 香农指出的信息熵的计算公式如下 H(x) = -∑p(xi)log(p(xi)) (i=1,2,..n) 设序列S长度为n，则 Hn=I(x)= log(x)= log n! (bit) （1） * 比较次数的理论下限 若对序列S的某两个元素A和B进行一次比较, 设S中无相等元素,比较结果将原序列S分为两个子序列S1和S2, 其中S1包含全部AB的排列, 而S2包含全部AB的情况。 定理1：经过两个元素的一次比较后, 序列的平均信息熵减少,但最多减少1 bit.即若比较后序列S1和S2的平均信息熵记为H1(x),则有 H(x) - 1≤H1(x)H(x) * 比较次数的理论下限 定理2：对于一个长度为n的完全无序的序列S ,采用直接比较的方法进行排序,至少需要比较[logn! ]次才能完成排序. 该定理表明，序列的信息熵即为排序所需要的比较次数的理论下界. * 比较次数的理论下限 根据式(1),一个长度为n的完全无序的序列所包含的信息熵为logn! (bit), 根据定理1,直接比较序列中的任意两个元素,一次最多能减少1bit信息熵. 排序结束后信息熵应为零. 因此,通过一次比较两个元素将序列的信息熵减小到零至少需要[logn! ]次才能完成. * 几种排序算法的分析 冒泡排序： 随着冒泡排序的进行，整个序列将变得越来越有序，位置颠倒的泡泡将越来越少；选择排序的每一趟选择中，你都会不断得到越来越大的数，同时在以后的比较中找到更大的数的概率也越来越低。 * 几种排序算法的分析 插入排序： ⒈ 从第一个元素开始，该元素可以认为已经被排序 ⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描 ⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置 ⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 ⒌ 将新元素插入到下一位置中 ⒍ 重复步骤2~5 * 几种排序算法的分析 插入排序 * 几种排序算法的分析 插入排序： 总是把新的数与已经排好的数按从大到小的顺序依次进行比较，可以想到新的数一开始就比前面所有的数中最大值还大的概率是相当小的 * 利用信息熵原理寻找高效的排序方法 上述算法的效率并不高，原因就在于算法过程中会出现越来越多概率严重不均的比较。 在比较a和b的时候，若a b和a b的概率是均等的，我们就可以获得log2=1（bit）的信息量，也就是单次比较可以获得的最大信息量。 了使比较次数达到最少,应当使 每次比较减少信息熵 达到或尽量接近1 bit. * 利用信息熵原理寻找高效的排序方法 推论：如果每次都像假设的这样的完美比较，即a b和a b的概率是均等的，那么N个元素只需要logN!次就排序完了。 而logN!近似于NlogN。这正是快排的复杂度。 “快速排序法”的基本思想是用递归 ，每进行一步都将一个大的集合划分为两个小的子集，然后对两个子集实施相同的算法。当两个子集都完成了排序之后再把它们重新粘合到一起。 * 霍尔 (Sir Charles Antony Richard Hoare) 是一位英国计算机科学家，他是著名的快速排序 (QuickSort) 的发明者。 他想到的第一个算法是后人称作“冒泡排序 (bubble sort)”的算法。他很快放弃了这个算法，因为它的速度比较慢。 快速排序 (Quicksort) 是霍尔想到的第二个算法。当 n 特别大的时候，显然步骤要少很多。这个算法是二十世纪七大算法之一，而他本人则被称为影响算法世界的十位大师之一。 * 利用信息熵原理寻找高效的排序方法 假定我们有一组10个数，我们希望将它们从小到大排列。 * 利用信息熵原理寻找高效的排序方法 我们首先从数列中随机挑出一个元素，称为 基准。