主讲人： 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2012 ，USTC 算法基础 主讲人： 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2012 ，USTC
第七讲 顺序统计学 内容提要： 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择 2019/7/24
问题描述 在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i个小的元素。 一个中位数是它所在集合的“中点元素”。 当n为奇数时，中位数是唯一的，i=( n + 1 ) / 2； 当n为偶数时，中位数有两个，即：i=n/2(下中位数)和i=n/2+1（上中位数） 不考虑n的奇偶性，中位数总出现在 处（下中位数）和 处（上中位数）。本书中所用的“中位数”指的是下中位数。 选择问题：从一个由n个不同数值构成的集合中，选择其第i个顺序统计量。 输入：一个包含n个（不同的）数的集合A和一个数i, 1≤ i ≤n 输出：元素 ，它恰大于A中其它i-1个元素。 2019/7/24
问题描述 选择问题可以在O(nlgn)时间内解决： 用堆排序或合并排序对输入数据进行排序 再在输出数组中标出第i个元素即可。 还有其他更快的算法。
第七讲 顺序统计学 内容提要： 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择 2019/7/24
最小值和最大值 最小/最大值：进行n-1次比较，时间复杂度为θ(n)； 假设集合放在数组A中，且length[A] = n。 MINIMUM ( A ) min ← A[1]; for i ← 2 to length[A] do if min > A[i] then min ← A[i] return min 总共比较了n - 1次，时间复杂度：O(n) 2019/7/24
最小值和最大值 同时找最小值和最大值 1）记录比较过程中遇到的最小值和最大值； 2）成对处理元素，先比较两个输入元素，把较小者与当前最小值比较，较大者与当前最大值比较（每对元素需要3次比较） MAX-MINIMUM ( A ) if length[A] is odd then min ← A[1]; max ← min; else min ← MIN( A[1], A[2] ), max ← MAX( A[1], A[2] ); i ++; while i ≤ length[A] min ← MIN( MIN(A[i], A[i+1]), min ) max ← MAX( MAX(A[i], A[i+1]), max ) i ← i+2; end return min, max 2019/7/24
最小值和最大值 如何设定当前最小值和最大值的初始值：依赖于n的奇偶性 总的比较次数： 如果n是奇数，那么总共做了 次比较 时间复杂度为：O(n) 2019/7/24
第七讲 顺序统计学 内容提要： 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择 2019/7/24
以期望线性时间做选择 基本思想：采用分治策略，借鉴快速排序的随机划分法，对输入数组进行递归划分，但是只处理划分的一边。 RANDOMIZED-SELECT ( A, p, r, i ) if p = r // 临界问题处理 then return A[p] q ← RANDOMIZED-PARTITION( A, p, r ) //进行划分，返回划分元下标 k ← q – p + 1 if i = k then return A[q]; else if i < k then return RANDOMIZED-SELECT ( A, p, q - 1, i ) else return RANDOMIZED-SELECT( A, q+1, r, i – k ) 2019/7/24
以期望线性时间做选择 2019/7/24
以期望线性时间做选择 时间复杂度分析： 2019/7/24
以期望线性时间做选择 2019/7/24
以期望线性时间做选择 2019/7/24
以期望线性时间做选择 2019/7/24
第七讲 顺序统计学 内容提要： 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择 2019/7/24
最坏情况线性时间的选择 基本思想：类似RandomizedSelect算法，通过对输入数组进行递归划分来找出所求元素，但是算法保证每次对数组的划分是个好划分 主要步骤： 2019/7/24
最坏情况线性时间的选择 2019/7/24
最坏情况线性时间的选择 时间复杂度分析： 由上页图示，可知至少有 的元素较x来得大。 同理，至少有3n/10 -6 的元素较x来得小。 如果Partition过，i ≠ k，则至多只要在7n/10+6个元素的情況下递归调用Select。 而先前找出 小组中位数的中位数时，只在n/5个元素的情况下递归调用 Select。 故T(n)=T( )+T(7n/10+6)+Θ(n), for n >= 140. 2019/7/24
最坏情况线性时间的选择 利用替换法，令T( n ) = O( cn ) 假设n>140时，c>=20a，上式就可以成立！ 2019/7/24
最坏情况线性时间的选择 2019/7/24
谢谢！ Q & A 作业： 9.1-1 9.3-6 2019/7/24