《算法设计与分析减治法精选课件.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析减治法精选课件.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于算法设计与分析关于算法设计与分析减治法减治法第一页，本课件共有63页2减治法的基本思想减治法的基本思想将规模为将规模为n的问题递的问题递减减为规模为为规模为n-1或或n/2的的子问题子问题,反复递减反复递减后对子问题分别求解后对子问题分别求解,再建立再建立子问题的解与原问题的解的关系。子问题的解与原问题的解的关系。第二页，本课件共有63页3减常数减常数(如如1):每此迭代规模减小每此迭代规模减小nn-1第三页，本课件共有63页4减因子减因子(如如1/2):每此迭代规模减半每此迭代规模减半nn/2第四页，本课件共有63页5减可变规模减可变规模:每此迭代减小的规模不同每此迭代减小的规模不同第五
2、页，本课件共有63页6减常量：减常量：5.1插入排序插入排序5.2深度优先查找与广度优先查找深度优先查找与广度优先查找5.3拓扑排序拓扑排序5.4生成组合对象的算法生成组合对象的算法5.5减常因子算法减常因子算法5.6减可变规模算法减可变规模算法第六页，本课件共有63页75.1 插入排序插入排序如何用减一法对一个数组如何用减一法对一个数组A0.n-1排序？排序？也就是如何建立也就是如何建立n规模与规模与n-1规模之间的关系？规模之间的关系？假设假设n-1规模的数组规模的数组A0.n-2已经解决，已经解决，则需要考虑元素则需要考虑元素An-1，在这个有序数组中处于何处在这个有序数组中处于何处？常
3、用的插入排序有：直接插入排序、折半插入排序常用的插入排序有：直接插入排序、折半插入排序它们划分的依据是在排好序的序列中寻找插入位置所使它们划分的依据是在排好序的序列中寻找插入位置所使用方法的不同。用方法的不同。第七页，本课件共有63页8直接插入排序举例直接插入排序举例待排序序列待排序序列89,45,68,90,29,34,17插入过程插入过程:89不需比较不需比较45,8945,68,8945,68,89,9029,45,68,89,9029,34,45,6889,9017,29,34,45,68,89,90插入次数插入次数=n-1=6比较次数比较次数=?第八页，本课件共有63页9直接插入排序
4、伪代码直接插入排序伪代码ALGORITHM InsertionSort(A0.n-1)/对给定序列进行直接插入排序对给定序列进行直接插入排序/输入：大小为输入：大小为n的无序序列的无序序列A/输出：按非递减排列的序列输出：按非递减排列的序列Afor i 1 to n-1 dotemp Aij i-1while j 0 and Aj temp doAj+1 Ajj j 1Aj+1 temp第九页，本课件共有63页10直接插入排序效率分析直接插入排序效率分析基本操作基本操作:比较比较比较次数比较次数C(n):最坏的情形是最坏的情形是严格递减的数组严格递减的数组每次插入每次插入,需比较已插入的所有元
5、素需比较已插入的所有元素,此时此时,第第i次插入次插入比较比较i个元素个元素,故故第十页，本课件共有63页11最好的情况？最好的情况？升序排列升序排列每次插入只需比较一次每次插入只需比较一次第十一页，本课件共有63页12平均效率的精确分析基于对无序元素的研究，对于随机序平均效率的精确分析基于对无序元素的研究，对于随机序列的数组，列的数组，第十二页，本课件共有63页13评价评价插入排序最差插入排序最差(n2)最优最优(n)平均平均(n2)合并排序最差合并排序最差(nlog2n)快速排序最优快速排序最优(nlog2n)最差最差(n2)平均平均(1.38nlog2n)选择排序选择排序(n2)冒泡排序
6、冒泡排序(n2)遇到遇到基本有序基本有序数组表现优异数组表现优异性能，可结合性能，可结合快速排序快速排序第十三页，本课件共有63页145.2 深度优先查找深度优先查找一个一个DFS输出序列是？输出序列是？a-c-d-f-b-e-g-h-i-j第十四页，本课件共有63页15在数据结构中如何表示图？在数据结构中如何表示图？第十五页，本课件共有63页16在深度优先遍历时需要使用到什么辅助结构？在深度优先遍历时需要使用到什么辅助结构？写出出栈和入栈的过程写出出栈和入栈的过程第十六页，本课件共有63页17深度优先搜索的效率与图的表示有关吗？深度优先搜索的效率与图的表示有关吗？对邻接矩阵表示的图：遍历的效
7、率为对邻接矩阵表示的图：遍历的效率为(V 2)对邻接链表表示的图：遍历的效率为对邻接链表表示的图：遍历的效率为(V+E)第十七页，本课件共有63页185.2 广度优先查找广度优先查找一个一个BFS输出序列是？输出序列是？a-c-d-e-f-b-g-h-j-i在广度优先遍历时需要使用到什么辅助结构？在广度优先遍历时需要使用到什么辅助结构？第十八页，本课件共有63页19广度优先搜索的效率与图的表示有关吗？广度优先搜索的效率与图的表示有关吗？对邻接矩阵表示的图：遍历的效率为对邻接矩阵表示的图：遍历的效率为(V 2)对邻接链表表示的图：遍历的效率为对邻接链表表示的图：遍历的效率为(V+E)第十九页，本
8、课件共有63页20总结总结DFSBFS数据结构数据结构临时栈临时栈(stack)队列队列(queue)顶点顺序的种类顶点顺序的种类两种顺序两种顺序一种顺序一种顺序邻接链表的效率邻接链表的效率邻接矩阵的效率邻接矩阵的效率应用应用判断是否有环判断是否有环判断是否连通判断是否连通求关节点求关节点判断是否有环判断是否有环判断是否连通判断是否连通求最短路径求最短路径(V V +E E )(V V +E E )(V V 2 2)(V V 2 2)第二十页，本课件共有63页215.3 拓扑排序拓扑排序在大学学习的过程中，各门课程的学习是有先在大学学习的过程中，各门课程的学习是有先后顺序的，有些课程需要先修课
9、程，有些则不需后顺序的，有些课程需要先修课程，有些则不需要；有些课程之间有先后的关系，有些课程则可要；有些课程之间有先后的关系，有些课程则可以并行的进行。问题要求确定一个学习方案使得以并行的进行。问题要求确定一个学习方案使得各门课程的学习能够有序进行。各门课程的学习能够有序进行。拓扑排序问题：拓扑排序问题：对给定的对给定的无环有向图无环有向图，要求按照某种顺序列出，要求按照某种顺序列出它的顶点序列，使图的每一条边的起点总在结束它的顶点序列，使图的每一条边的起点总在结束顶点之前。顶点之前。第二十一页，本课件共有63页22Example:Orderthemfromlowertohigher,con
10、sistentwithfoodchainF鱼H人M小虾S羊W小麦P微生物T虎第二十二页，本课件共有63页23求拓扑序列的方法求拓扑序列的方法1方法方法1、应用、应用DFS的出栈次序。的出栈次序。DFS序列：序列：C1-C3-C4-C5-C2出栈序列：出栈序列：C5-C4-C3-C1-C2拓扑排序：拓扑排序：C2-C1-C3-C4-C5思考为什么这个算法是有效的？思考为什么这个算法是有效的？C1C3C2C5C4第二十三页，本课件共有63页24求拓扑序列的方法求拓扑序列的方法2方法方法2、如何用减一法？、如何用减一法？N规模和规模和n-1规模如何建立联系？规模如何建立联系？容易得到一个拓扑序列：容
11、易得到一个拓扑序列：P-W-S-M-F-H-T即：即：微生物微生物-小麦小麦-羊羊-小虾小虾-鱼鱼-人人-虎虎F鱼H人M小虾S羊W小麦P微生物T虎第二十四页，本课件共有63页255.4 生成组合对象的算法生成组合对象的算法1、生成排列、生成排列排列问题指的是对于给定的多个元素求排列问题指的是对于给定的多个元素求其中各种可能的序列。为了简单起见，这其中各种可能的序列。为了简单起见，这里仅仅考虑里仅仅考虑1到到n之间的整数的排列问题。之间的整数的排列问题。下面介绍三种生成方法：下面介绍三种生成方法：（1）插入法）插入法（2）Johnson-Trotter法法（3）字典顺序法）字典顺序法第二十五页，
12、本课件共有63页26插入法生列排列插入法生列排列如何用减一法构造如何用减一法构造n规模与规模与n-1规模问题之间的关规模问题之间的关系？系？将第将第n个数插入到个数插入到(n-1)!个排列的个排列的n个可能位置中个可能位置中去。去。第二十六页，本课件共有63页27插入法生列排列插入法生列排列举例：求举例：求n=3的排列的排列方法：方法：在在n=2的排列中插入的排列中插入3，在在n=1的排列中插入的排列中插入2。构造过程（从底向上）：构造过程（从底向上）：在在1中从右到左插入中从右到左插入2得到得到12，21在在12中从右到左插入中从右到左插入3得到得到123，132，312在在21中从右到左插
13、入中从右到左插入3得到得到213，231，321于是得于是得123，132，312，213，231，321第二十七页，本课件共有63页28插入法生列排列插入法生列排列-优点优点满足满足最小变化最小变化的要求的要求第二十八页，本课件共有63页29Johnson-Trotter 法生成排列法生成排列其实有的算法并不需要知道规模其实有的算法并不需要知道规模n-1的排列就可以直接得的排列就可以直接得到规模到规模n的排列结果，的排列结果，Johnson-Trotter算法就是其中一种。算法就是其中一种。利用这一算法求得的排列序列还是相邻序列变化最小的一个利用这一算法求得的排列序列还是相邻序列变化最小的一
14、个序列集合，也就是说序列集合，也就是说下一个序列与上一个序列仅仅交换下一个序列与上一个序列仅仅交换了两个元素的位置了两个元素的位置。第二十九页，本课件共有63页30J-T方法举例方法举例在排列的每一分量上画一个箭头。在排列的每一分量上画一个箭头。移动元素移动元素：如果分量：如果分量k的箭头指向一个相邻的较的箭头指向一个相邻的较小元素，则该分量在排列中是移动的。小元素，则该分量在排列中是移动的。求最大的移动整数求最大的移动整数k，不断移动元素，直到没有，不断移动元素，直到没有元素可移动为止，掉转所有大于元素可移动为止，掉转所有大于k的整数方向。的整数方向。例例n=3,从从123开始：开始：第三十
15、页，本课件共有63页31字典顺序生成排列字典顺序生成排列尽管尽管Johnson-Trotter算法非常高效，但是似乎不算法非常高效，但是似乎不是那么直观，不太符合人们的思维习惯。事实上是那么直观，不太符合人们的思维习惯。事实上比较自然的算法称为比较自然的算法称为“字典排序（字典排序（lexicographicorder）算法）算法”，它是根据单词在字典中的排列，它是根据单词在字典中的排列顺序得到的算法。顺序得到的算法。第三十一页，本课件共有63页32字典生成顺序举例字典生成顺序举例例例n=3在在1，2，3中按字典顺序选择：中按字典顺序选择：123132213231312321第三十二页，本课件
16、共有63页33基本思想：基本思想：从右到左扫描一个当前排列，寻找第一对连续的从右到左扫描一个当前排列，寻找第一对连续的元素元素ai和和ai+1，aiai+1ai+1及后面的元素什么特点？及后面的元素什么特点？在在ai+1及后面的元素中寻找大于及后面的元素中寻找大于ai的最小数字的最小数字放到放到i的位置上的位置上ai，ai+1。an按升序从按升序从i+1位置排到位置排到n第三十三页，本课件共有63页342、生成子集、生成子集考虑如何用减一法生成规模为考虑如何用减一法生成规模为n的集合的所的集合的所有子集？有子集？如何建立如何建立n规模和规模和n-1规模的关系规模的关系在在n-1规模集合的所有子
17、集中添加第规模集合的所有子集中添加第n个元个元素素第三十四页，本课件共有63页35减治法生成幂集减治法生成幂集例例n=3方法：方法：在在n=2的幂集中加入元素的幂集中加入元素3，在在n=1的幂集中加入元素的幂集中加入元素2在在n=0的幂集中加入元素的幂集中加入元素1 ,1/n=1,1,2,1,2/加入元素加入元素2 ,1,2,1,2,3,1,3,2,3,1,2,3/加入元素加入元素3第三十五页，本课件共有63页36位串法生成幂集位串法生成幂集这是一个直接解决该问题的方法，可以对较小的集合这是一个直接解决该问题的方法，可以对较小的集合生成幂集生成幂集例例n=3,元素为元素为a1,a2,a3方法：
18、方法：每一个子集与一个每一个子集与一个3位二进制串位二进制串b1b2b3对应，对应，ai属于该子集时，属于该子集时，bi=1,否则否则bi=0二进制串：二进制串：000,001,010,011,100,101,110,111对应子集：对应子集：,a3,a2,a2,a3,a1,a1,a3,a1,a2,a1,a2,a3第三十六页，本课件共有63页375.5 减常因子法减常因子法已有例子已有例子折半查找、用平方求幂折半查找、用平方求幂注意：注意：不要指望有许多这种类型的例子不要指望有许多这种类型的例子，因为这种算法，因为这种算法的效率常常是对数的，速度非常快，并不会时常的效率常常是对数的，速度非常快
19、，并不会时常出现，不以出现，不以2为因子化简的情况更是少之又少。为因子化简的情况更是少之又少。第三十七页，本课件共有63页381 1、假币问题、假币问题 有有n n个金币，其中一个是假币。这个假币的重个金币，其中一个是假币。这个假币的重量比真币的重量要量比真币的重量要轻一点轻一点，所有，所有n-1n-1个金币的重个金币的重量是一样的。现在你有量是一样的。现在你有一架一架天平，天平，设计高效的算设计高效的算法（法（用最少的用最少的使用天平使用天平次数次数）找出那个假的金币。找出那个假的金币。考虑用蛮力法，如何解？时间效率类型是？考虑用蛮力法，如何解？时间效率类型是？减治法？可类比于折半查找。减治
20、法？可类比于折半查找。第三十八页，本课件共有63页39假币问题解法假币问题解法1、用减治法、用减治法(减半）减半）把把n个硬币分为两堆，每堆个硬币分为两堆，每堆 n/2 个，每次称一堆。个，每次称一堆。请写出递推式请写出递推式易见易见W(1)=0W(n)=W(n/2)+1解得解得W(n)=log2n 第三十九页，本课件共有63页40假币问题解法假币问题解法2、用减治法、用减治法(减减n/3）把把n个硬币分为三堆，每堆个硬币分为三堆，每堆 n/3 个，每次称任意二堆。个，每次称任意二堆。易见易见W(1)=0W(n)=W(n/3)+a解得解得W(n)=log3n 结果比减半法更好。结果比减半法更好
21、。是否分堆数越多越好？是否分堆数越多越好？第四十页，本课件共有63页412、俄式乘法、俄式乘法/俄国农民法俄国农民法非主流算法非主流算法设设n、m是整数，以是整数，以n为实例规模的度量。为实例规模的度量。若若n为偶数，则为偶数，则nm=(n/2)2m若若n为奇数，则为奇数，则nm=(n-1)/2)2m+m以以1m=m为算法停止的条件。为算法停止的条件。第四十一页，本课件共有63页42俄国农民法举例俄国农民法举例:5065nm分析分析.50652513012260+13065203104012080+10402080+2080=3250整个算法只包括整个算法只包括折半折半加倍加倍相加相加优势？优
22、势？第四十二页，本课件共有63页433 3、约瑟夫斯问题、约瑟夫斯问题约瑟夫斯是公元约瑟夫斯是公元1 1世纪的犹太历史学家，他领导了世纪的犹太历史学家，他领导了反抗罗马人的武装起义，但是失败了。反抗罗马人的武装起义，但是失败了。他和四十名犹太士兵被罗马人围困在一个山洞中。他和四十名犹太士兵被罗马人围困在一个山洞中。这四十个士兵宁死不屈，决定杀身成仁。但约瑟夫这四十个士兵宁死不屈，决定杀身成仁。但约瑟夫斯不想，但又不便公开反对。斯不想，但又不便公开反对。于是提出一个方法，就是四十一个人站成一个圈，于是提出一个方法，就是四十一个人站成一个圈，从某人开始数起，凡数到三的人就让大家成全他升从某人开始数
23、起，凡数到三的人就让大家成全他升天，这样下去直到剩下最后一个人，这个人就自杀。天，这样下去直到剩下最后一个人，这个人就自杀。大家都没有意见，于是约瑟夫斯就挑选了第大家都没有意见，于是约瑟夫斯就挑选了第3131号的号的位置。结果所有人都死了，剩下他一个活下来投降位置。结果所有人都死了，剩下他一个活下来投降了罗马人。这也是约瑟夫斯问题的最初提法。了罗马人。这也是约瑟夫斯问题的最初提法。第四十三页，本课件共有63页44约瑟夫斯问题约瑟夫斯问题 约瑟夫斯问题的一般提法：约瑟夫斯问题的一般提法：设有设有n个以个以1、2、n编号的人，按编号顺序围成一编号的人，按编号顺序围成一圈，从圈，从1号开始报数，每数
24、到号开始报数，每数到m就淘汰一人，问最后被淘就淘汰一人，问最后被淘汰的人是几号呢？汰的人是几号呢？令令L(n,m)为上述为上述最后被淘汰的人的号码最后被淘汰的人的号码，即幸存者的即幸存者的初始位置。初始位置。则可以将最初的约瑟夫斯问题写成则可以将最初的约瑟夫斯问题写成L(41,3)31。第四十四页，本课件共有63页45减治法的体现在于，整个圆圈走一遍后，规模减减治法的体现在于，整个圆圈走一遍后，规模减小小1m如如m=2，走一圈后生成同样问题的规模减，走一圈后生成同样问题的规模减1/2的实例的实例m=3，走一圈后生成同样问题的规模减，走一圈后生成同样问题的规模减1/3的实例的实例考虑考虑m=2时
25、，如何得到幸存者的初始位置？时，如何得到幸存者的初始位置？当当n为偶数时，某人前一轮的位置为偶数时，某人前一轮的位置=新位置新位置2-1为什么？为什么？幸存者的初始位置幸存者的初始位置L(n,2)=2L(n/2,2)-1当当n为奇数时，为奇数时，L(n,2)=2L(n-1)/2,2)+1解这两个递推式获得幸存者的初始位置的表达式。解这两个递推式获得幸存者的初始位置的表达式。第四十五页，本课件共有63页46约瑟夫斯问题分析约瑟夫斯问题分析还可使用前向替代法，找出一个模式还可使用前向替代法，找出一个模式即即L(n,2)有什么规律？有什么规律？L(2,2)=1=20+12=210L(3,2)=3=2
26、1+13=211L(4,2)=1=20+14=220L(5,2)=3=21+15=221L(6,2)=5=22+16=222L(7,2)=7=23+17=223L(13,2)=11=25+113=235L(n,2)2b1n=2ab(而而a必须尽可能大必须尽可能大)例如当例如当n=100，则，则100可以写成可以写成2568，也可以写成，也可以写成2636，但是不能再写成，但是不能再写成27的了，的了，所以，所以，a=6，而，而b=36。第四十六页，本课件共有63页47约瑟夫斯问题分析约瑟夫斯问题分析当当m3、4、时，有没有公式呢？时，有没有公式呢？但存在一个但存在一个L(n,m)递推公式：递推
27、公式：L(1,m)1L(k1,m)L(k,m)m(modn+1)第四十七页，本课件共有63页48约瑟夫问题集约瑟夫问题集第一题：猴子选大王。第一题：猴子选大王。题目：有题目：有M个猴子围成一圈，每个有一个编号，编号从个猴子围成一圈，每个有一个编号，编号从1到到M。打算从。打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始，每隔始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。要求：从键个，数到的猴子出圈，最后剩下来的就是大王。要求：从键盘输入盘输入M，N，编程计算哪一个编号的猴子成为大王。，编程计算哪一个编号的猴子成为
28、大王。第二题：第二题：设有设有N个人围成一圏，并且按照顺时针方向从个人围成一圏，并且按照顺时针方向从1到到N编号，编号，由第由第S个人开始进行从个人开始进行从1到到M报数，报数到第报数，报数到第M个人时，此人出圏，再从个人时，此人出圏，再从下一个人重新开始从下一个人重新开始从1到到M报数，如此进行下去，直到所有的人都出报数，如此进行下去，直到所有的人都出圏为止。现在要求编程按照出圏的顺序，打印这圏为止。现在要求编程按照出圏的顺序，打印这N个人的顺序表。个人的顺序表。第四十八页，本课件共有63页49第三题：狸捉兔子第三题：狸捉兔子围绕着山顶有个洞，狐狸要吃兔子，兔子说：围绕着山顶有个洞，狐狸要吃
29、兔子，兔子说：“可以，但必须找到我，可以，但必须找到我，我就藏身于这十个洞我就藏身于这十个洞中，你从号洞出发，先到号洞找，第二次中，你从号洞出发，先到号洞找，第二次隔个隔个洞找，第三次隔个洞找，以后如此类洞找，第三次隔个洞找，以后如此类推，次数不限。推，次数不限。”但狐狸从早到晚进进出出了但狐狸从早到晚进进出出了次，仍没有找到兔子。问兔子究竟藏在哪次，仍没有找到兔子。问兔子究竟藏在哪个洞里？个洞里？第四十九页，本课件共有63页50第四题：慈善的约瑟夫第四题：慈善的约瑟夫你一定听说过约瑟夫问题吧？即从你一定听说过约瑟夫问题吧？即从N个人找出唯一的幸存个人找出唯一的幸存者。者。现在老约瑟夫将组织一
30、个皆大欢喜的新游戏，假设现在老约瑟夫将组织一个皆大欢喜的新游戏，假设N个人个人站成一圈，从第站成一圈，从第1人开始交替的去掉游戏者，人开始交替的去掉游戏者，但只是暂时去但只是暂时去掉，直到最后剩下唯一的幸存者为止。掉，直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人得到幸存者选出后，所有比幸存者号码高的人每人得到1个个金币，永久性离开。其余剩下的将重复以上的游戏过程，金币，永久性离开。其余剩下的将重复以上的游戏过程，比比幸存者号码主的人每人得到幸存者号码主的人每人得到1个金币后离开。经过这们的个金币后离开。经过这们的过程后，一旦人数不再减少，则最后剩下的那些人将得过程后，
31、一旦人数不再减少，则最后剩下的那些人将得到到2个金币。请你计算一下老约瑟夫一共要付出多个金币。请你计算一下老约瑟夫一共要付出多少钱？少钱？输入：输入：N输出：金币数。输出：金币数。第五十页，本课件共有63页51第五题：第五题：50枚棋子围成圆圈，编上号码枚棋子围成圆圈，编上号码1，2，3，每隔一枚棋子取出一枚，要求最后留下的一每隔一枚棋子取出一枚，要求最后留下的一枚棋子的号码是枚棋子的号码是42，那该从几号棋子开始取呢？，那该从几号棋子开始取呢？第六题：变形猴子选大王第六题：变形猴子选大王题目：有题目：有n个猴子选大王，选举办法如下：从头个猴子选大王，选举办法如下：从头到尾到尾1，2，3报数，
32、凡报到报数，凡报到3的退出，余下的从的退出，余下的从尾到头尾到头1，2，3报数，凡报报数，凡报3的退出。如的退出。如此类推，当剩下两只猴子时，取这时报此类推，当剩下两只猴子时，取这时报1的为王，的为王，若想当猴王，请问当初应站在什么位置？若想当猴王，请问当初应站在什么位置？第五十一页，本课件共有63页525.6 减可变规模算法减可变规模算法1、计算中值和选择问题、计算中值和选择问题选择问题：选择问题：求一个求一个n数组的第数组的第k个最小元素。个最小元素。一些特殊的情况一些特殊的情况k=1k=nk=n/2，该元素被称为中值，该元素被称为中值例如，例如，数组数组4,1,10,9,7,12,8,2
33、,15,求第求第5小的元素小的元素你能想到什么方法？你能想到什么方法？排序排序第五十二页，本课件共有63页53数组数组4,1,10,9,7,12,8,2,15,求中值元素求中值元素即求第即求第k=9/2=5小的元素。小的元素。使用快速排序中的分区算法使用快速排序中的分区算法先数组先数组4,1,10,9,7,12,8,2,15分区分区,中轴中轴=41,2，4，9,7,12,8,10,15,s=3因因sk,在在8,7中找中找7,8此时，此时，s=k=5,中值是中值是8第五十三页，本课件共有63页54效率分析效率分析平均情况下：平均情况下：和快速排序比和快速排序比要高效要高效严格的数学分析表明，严格
34、的数学分析表明，平均情况下的效率和每次平均情况下的效率和每次都消减一半情况下的效率是完全相同的都消减一半情况下的效率是完全相同的。每次都消减一半的递推式是？每次都消减一半的递推式是？C(n)=C(n/2)+(n+1)第五十四页，本课件共有63页55最差情况？最差情况？第五十五页，本课件共有63页562、插值查找（有序数组）、插值查找（有序数组）与折半查找的不同与折半查找的不同在数组在数组2,5,12,23,39,50,66,78,90,100,150中查找中查找key=12在电话号码本上查找在电话号码本上查找brown与与smith，用折半查找如何做，用折半查找如何做？缺点如何？缺点如何？查找
35、时考虑查找时考虑key的特点的特点但如何确定但如何确定key是偏向于数组的左边还是右边？是偏向于数组的左边还是右边？在数组在数组2,5,12,23,39,50,66,78,90,100,150中查找中查找key=12第五十六页，本课件共有63页57第五十七页，本课件共有63页58设某次迭代处理的是数组最左边元素设某次迭代处理的是数组最左边元素Al和最右和最右边元素边元素Ar之间的部分，要查找的键值为之间的部分，要查找的键值为v。写出过点写出过点(l,Al)和点和点(r,Ar)的的直线方程直线方程，取，取y=v，求出横坐标求出横坐标x，比较，比较Ax与与v的值，决定是停止，的值，决定是停止，还是
36、在还是在l与与x-l之间或之间或x+l与与r之间继续查找。之间继续查找。第五十八页，本课件共有63页59关于折半查找和插值查找的说明关于折半查找和插值查找的说明对于小的文件对于小的文件折半查找可能更好一些折半查找可能更好一些对于更大的文件对于更大的文件和那些和那些访问成本非常高访问成本非常高的的应用，的的应用，插值查找更值得考虑。插值查找更值得考虑。平均来说插值查找的键值比较次数平均来说插值查找的键值比较次数log2log2n+1第五十九页，本课件共有63页603、二叉查找树查找和插入、二叉查找树查找和插入所谓的二叉查找树，它或者是一棵空树，或者所谓的二叉查找树，它或者是一棵空树，或者满足以下
37、的性质：满足以下的性质：每个结点作为搜索对象，它的关键字是互不相同的。每个结点作为搜索对象，它的关键字是互不相同的。对于树上的所有结点，如果它有左子树，那么左子树上对于树上的所有结点，如果它有左子树，那么左子树上所有结点的关键字都小于该结点的关键字。所有结点的关键字都小于该结点的关键字。对于树上的所有结点，如果它有右子树，那么右子对于树上的所有结点，如果它有右子树，那么右子树上所有结点的关键字都大于该结点的关键字。树上所有结点的关键字都大于该结点的关键字。第六十页，本课件共有63页61对一般搜索表，也可以建立它相对应的二对一般搜索表，也可以建立它相对应的二叉搜索树，并利用它作为数据结构进行搜叉搜索树，并利用它作为数据结构进行搜索，这样的算法称为二叉搜索树搜索算法。索，这样的算法称为二叉搜索树搜索算法。它的优势是很明显的，它不但能够适应静它的优势是很明显的，它不但能够适应静态的搜索环境，也能够很好地运用到动态态的搜索环境，也能够很好地运用到动态环境中。环境中。但二叉查找树在最坏的情况下，但二叉查找树在最坏的情况下，n个元素的个元素的树的高度等于树的高度等于n，查找效率为，查找效率为(n)，平均效，平均效率则可达到率则可达到(logn).第六十一页，本课件共有63页62小结小结第六十二页，本课件共有63页感感谢谢大大家家观观看看第六十三页，本课件共有63页