- 1、本文档共36页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
第4章 不基於比较的排序算法1序言 2比较排序的复杂度下界 3不基於比较的线性时间排序算法 19计数排序 19基数排序 27桶排序 31
21.序言可以证明,任何比较排序在最坏情况时需要至少lg(n!)?nlgn次比较。要想有更快的排序算法,必须考虑不基於比较的排序。不基於比较的排序往往有额外的条件限制。主要討论: 计数排序 基数排序 桶排序
32.比较排序的复杂度下界 决策树模型及最坏情况下界? 很多问题的决策是对输入数据作一系列某个操作决定的。每次操作会有若干个可能的结果,而下次操作如何进行是根据这一次操作的结果而定,直到得到答案。这可用一个决策树来描述。任何基於比较的排序都是通过一系列数字间的比较来决定输入数据之间大小关系的,因此可以用一棵决策树来描述。证明排序问题的下界,我们只需考虑输入的n个数都不相等的情况。这是因为针对一个特殊情况的下界也一定是包含所有情况的下界。我们将证明,即使需要排序的n个数都不相等,任何基於比较的排序算法,在最坏情况时,都必须做至少?lg(n!)??nlgn次比较。
4例(图4.1):一个把a1,a2,a3排序的决策树有n个不同数的序列中,最小的数称为第1顺序数,第2小的数称为第2顺序数,…,第n个小的数(即最大的数)称为第n顺序数。排序就是确定在原序列中,那个是第1顺序数,那个是第2顺序数,…,那个是第n顺序数。所以,排序的本质是给出n个顺序数在原序列中的一个排列。(接下页)
5决策树模型及最坏情况下界(继续)每个叶结点代表了一个从输入序列A[1],A[2],…,A[n],到输出序列B[1]B[2]…B[n]的映射。如果B[j]=A[i],那么,A[i]就是第j顺序数(1?i?n)。我们可以定义这个映射函数为:?(i)=j。比如,图4-1中叶结点(1,3,2)表示A[1]A[3]A[2]。这个映射函数是:?(1)=1,?(2)=3,?(3)=2。因为输入的n个数都不相等,它们只能有一个排序结果,所以一个叶结点只能代表一个映射。因为一个映射正好等于一个n个元素的全排列,所以有n!个不同的映射。因此,决策树必须至少有n!个叶子来代表这些不同的映射。如n个数不等,可证明排序决策树必须正好有n!个叶子(见书)。
6定理4.1任一个比较排序算法,在最坏情况时,需要至少?lg(n!)?次比较。证明:由上面讨论,任何比较排序算法所对应的决策树必须有n!个叶子。设这个决策树的高是h。因为高度为h的二叉树最多有2h个叶子,所以必有关系:2h≥n!,也就是h?lg(n!)。因为h是整数,所以有h??lg(n!)?。这说明,有一个叶子的深度(depth)是h。那么,如果算法从树根开始,经过一系列比较操作后到达这个叶子时,算法必定作了h次比较。这是因为,算法要做一次比较才可以沿路径前进一步。所以,一个比较排序算法,在最坏情况时,需要至少h=?lg(n!)?次比较。?注:因lg(n!)?nlgn,通常也说,比较排序的下界是nlgn。
7下界应用举例例4.1 假设我们需要判定数组A[1..n]中的n个数是否有相同的数字,那么,在最坏情况时,任何基于比较的算法需要至少lg(n!)次比较。证明:假设算法A是这样的一个算法。设输入的A[1..n]含n个不同数。 这些数可以排序为:b1b2…bn。我们不需真的去排序,但这个递增序列肯定存在。算法A必定会判定A[1..n]中没有相同的数字。我们断定:算法A一定比较了b1和b2。我们用反证法证明这点。假设算法A没有比较b1和b2,却判定A[1..n]没有相同的数字,那么我们把b2改动一下,让b2等于b1,b2=b1,其余数不变。然后,把这改动后的数组A[1..n]再让这个算法A去判定。(接下页)
8下界应用举例(证明继续)显然,这个改动不会改变任何两个数,bi和bj(1?ij?n)的比较结果,除非i=1,j=2。因为前一次判定时,算法没有比较b1和b2,所以算法这一次会重复所有前一次的比较,也不会比较b1和b2。那么,算法A必定察觉不到我们的改动,而仍然会判定数组中没有相同的数字。显然,这就错了。反证法成功。所以,算法A必定要比较b1和b2。同理,如果b3是第3小的数,那么这个算法必定要比较b2和b3。以此类推,这个算法必须比较序列中每两个相邻的数字。这就意味着,根据这个算法的比较结果,我们可以把这n个不同数字排序。因为基于比较的排序至少需要lg(n!)次比较,所以这个算法A也需要至少lg(n!)次比
您可能关注的文档
- 计算机算法基础 第2版 课件 第1章 概述.pptx
- 计算机算法基础 第2版 课件 第2章 分治法.pptx
- 计算机算法基础 第2版 课件 第3章 基于比较的排序算法.pptx
- 计算机算法基础 第2版 课件 第5章 中位数和任一顺序数的选择.pptx
- 计算机算法基础 第2版 课件 第6章 动态规划.pptx
- 计算机算法基础 第2版 课件 第7章 贪心算法.pptx
- 计算机算法基础 第2版 课件 第8章 图的周游算法.pptx
- 计算机算法基础 第2版 课件 第9章 图的最小支撑树.pptx
- 计算机算法基础 第2版 课件 第10章 单源最短路径.pptx
- 计算机算法基础 第2版 课件 第11章 网络流.pptx
文档评论(0)