最坏情况线性时间的选择课件.ppt

1、University of Science and Technology of China主讲人：主讲人：吕敏吕敏Email: Spring 2012，USTC算法基础算法基础University of Science and Technology of China2023-2-142第七讲第七讲 顺序统计学顺序统计学内容提要：内容提要：p最小值和最大值最小值和最大值p 以期望线性时间做选择以期望线性时间做选择p 最坏情况线性时间的选择最坏情况线性时间的选择University of Science and Technology of China问题描述问题描述p 在一个由在一个由n个元素组成

2、的集合中，个元素组成的集合中，第第i个顺序统计量个顺序统计量是该集合中第是该集合中第i个小的元素。个小的元素。p 一个一个中位数中位数是它所在集合的是它所在集合的“中点元素中点元素”。当当n为奇数时，中位数是唯一的，为奇数时，中位数是唯一的，i=(n+1)/2；当当n为偶数时，中位数有两个，即：为偶数时，中位数有两个，即：i=n/2(下中位数下中位数)和和i=n/2+1（上中位数）（上中位数）不考虑不考虑n的奇偶性，中位数总出现在的奇偶性，中位数总出现在 处（处（下中位数下中位数）和）和 处（处（上中位数上中位数）。本书中所用的）。本书中所用的“中位数中位数”指的是下中位数指的是下中位数。p

3、选择问题：从一个由选择问题：从一个由n个不同数值构成的集合中，选择其第个不同数值构成的集合中，选择其第i个顺个顺序统计量。序统计量。输入：一个包含输入：一个包含n个（不同的）数的集合个（不同的）数的集合A和一个数和一个数i,1 i n 输出：元素输出：元素 ，它恰大于，它恰大于A中其它中其它i-1个元素。个元素。2023-2-14312ni12ni xAUniversity of Science and Technology of China问题描述问题描述 选择问题可以在选择问题可以在O(nlgn)时间内解决：时间内解决：用堆排序或合并排序对输入数据进行排序用堆排序或合并排序对输入数据进行排

4、序再在输出数组中标出第再在输出数组中标出第i个元素即可。个元素即可。还有其他更快的算法。还有其他更快的算法。University of Science and Technology of China2023-2-145第七讲第七讲 顺序统计学顺序统计学内容提要：内容提要：p 最小值和最大值最小值和最大值p 以期望线性时间做选择以期望线性时间做选择p 最坏情况线性时间的选择最坏情况线性时间的选择University of Science and Technology of China最小值和最大值最小值和最大值p 最小/最大值：进行进行n-1n-1次比较，时间复杂度为次比较，时间复杂度为(n(n

5、)；p 假设集合放在数组假设集合放在数组A中，且中，且lengthA=n。2023-2-146MINIMUM(A)1 min A1;2 for i 2 to lengthA3 do if min Ai4 then min Ai5 return min总共比较了总共比较了n -1-1次，时间复杂度：次，时间复杂度：O(n)University of Science and Technology of China最小值和最大值最小值和最大值p 同时找最小值和最大值同时找最小值和最大值1）记录比较过程中遇到的最小值和最大值；）记录比较过程中遇到的最小值和最大值；2）成对处理元素，先比较两个输入元素，

6、把较小者与当前最小值比较）成对处理元素，先比较两个输入元素，把较小者与当前最小值比较，较大者与当前最大值比较（每对元素需要，较大者与当前最大值比较（每对元素需要3次比较）次比较）2023-2-147MAX-MINIMUM(A)1if lengthA is odd2 then min A1;max min;3 else min MIN(A1,A2),max MAX(A1,A2);4i+;5while i lengthA6 min MIN(MIN(Ai,Ai+1),min)7 max MAX(MAX(Ai,Ai+1),max)8 i i+2;9end 10 return min,maxUniver

7、sity of Science and Technology of China最小值和最大值最小值和最大值 如何设定当前最小值和最大值的初始值：如何设定当前最小值和最大值的初始值：依赖于依赖于n的奇偶性的奇偶性 如果如果n是奇数，将最小值和最大值都设为第一个元素的值；是奇数，将最小值和最大值都设为第一个元素的值；如果如果n是偶数，就对前两个元素做一次比较，以决定最小值和最大值是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初始值。的初始值。总的比较次数：总的比较次数：p 如果如果n是奇数，那么总共做了是奇数，那么总共做了 次比较次比较p 如果如果n是偶数，总共做了是偶数，总共做了 次比

8、较。次比较。2023-2-1482/3 n22/3n时间复杂度为：时间复杂度为：O(n)University of Science and Technology of China2023-2-149第七讲第七讲 顺序统计学顺序统计学内容提要：内容提要：p 最小值和最大值最小值和最大值p 以期望线性时间做选择以期望线性时间做选择p 最坏情况线性时间的选择最坏情况线性时间的选择University of Science and Technology of China以期望线性时间做选择以期望线性时间做选择p 基本思想基本思想：采用分治策略，借鉴快速排序的随机划分法，对输入采用分治策略，借鉴快速排序

9、的随机划分法，对输入数组进行递归划分，但是只处理划分的一边。数组进行递归划分，但是只处理划分的一边。2023-2-1410RANDOMIZED-SELECT(A,p,r,i)1if p=r /临界问题处理2 then return Ap3q RANDOMIZED-PARTITION(A,p,r)/进行划分，返回划分元下标4k q p+15if i=k6 then return Aq;7else if i=140.2023-2-1419133262 510nn 5n5nUniversity of Science and Technology of China最坏情况线性时间的选择最坏情况线性时间的选择p 利用替换法，令T(n)=O(cn)2023-2-1420/5(7/106)/57/106 9/107 (/107)/107 ,0T nc ncnancncc ncancncancncancncncancn if!假设n140时，c=20a，上式就可以成立！University of Science and Technology of China最坏情况线性时间的选择最坏情况线性时间的选择2023-2-1421University of Science and Technology of China谢谢！谢谢！2023-2-1422Q&A 作业：作业：9.1-1 9.3-6