中国科学技术大学：《算法基础》课程教学资源（PPT课件讲稿）第七讲 顺序统计学（主讲人：吕敏）

第七讲顺序统计学 内容提要 口最小值和最大值 口以期望线性时间做选择 口最坏情况线性时间的选择 2021/1/26

2021/1/26 2 第七讲 顺序统计学 内容提要： 最小值和最大值  以期望线性时间做选择  最坏情况线性时间的选择

问题描述 口在一个由n个元素组成的集合中,第个顺序统计量是该集合中第i 个小的元素。 口一个中位数是它所在集合的“中点元素”。 √当n为奇数时,中位数是唯一的,i(n+1)/2; 当n为偶数时,中位数有两个,即:i=n2(下中位数和n/2+1(上中位数) √不考虑n的奇偶性,中位数总出现在;=n+1\(下中位数)和=/"217 处(上中位数)。本书中所用的“中位数”指的是下中位数。 口选择问题:从一个由n个不同数值构成的集合中,选择其第个顺 序统计量 √输入:一个包含n个(不同的)数的集合A和一个数1≤isn 输出:元素x∈A,它恰大于A中其它1个元素 2021/1/26

问题描述  在一个由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个元素。 2021/1/26 3 1 2 n i   + =   1 2 n i   + =   x A 

问题描述 >选择问题可以在O(mgm)时间内解决: 用堆排序或合并排序对输入数据进行排序 >再在输出数组中标出第诠个元素即可。 还有其他更快的算法

问题描述 ➢ 选择问题可以在O(nlgn)时间内解决： ➢用堆排序或合并排序对输入数据进行排序 ➢再在输出数组中标出第i个元素即可。 ➢ 还有其他更快的算法

第七讲顺序统计学 内容提要 口最小值和最大值 口以期望线性时间做选择 口最坏情况线性时间的选择 2021/1/26

2021/1/26 5 第七讲 顺序统计学 内容提要：  最小值和最大值  以期望线性时间做选择  最坏情况线性时间的选择

最小值和最大值 口最小/最大值:进行n-1次比较,时间复杂度为(n); 口假设集合放在数组A中,且 length=n MINIMUM (A) 1min←Al; 2fori←2 to length 3 do if min>Ai 4 then min←A 5 return min 总共比较了n-1次,时间复杂度:O(n) 2021/1/26

最小值和最大值  最小/最大值：进行n-1次比较，时间复杂度为θ(n)；  假设集合放在数组A中，且length[A] = n。 2021/1/26 6 MINIMUM ( A ) 1 min ← A[1]; 2 for i ← 2 to length[A] 3 do if min > A[i] 4 then min ← A[i] 5 return min 总共比较了n - 1次，时间复杂度：O(n)

最小值和最大值 口同时找最小值和最大值 )记录比较过程中遇到的最小值和最大值; 2)成对处理元素,先比较两个输入元素,把较小者与当前最小值比较 ,较大者与当前最大值比较(每对元素需要3次比较) MAX-MINIMUM (A) 1 if length al is odd 2 then min←A[l;max←min; 3 else min MIN(A1, A2)), max+ MAX(A1, A2); 5 while is length min MN( MN(AG, Ali+lD, min max MAX( MAX(Ail, Ai+lD, max 9 end 10 return min, max 2021/1/26

最小值和最大值  同时找最小值和最大值 1）记录比较过程中遇到的最小值和最大值； 2）成对处理元素，先比较两个输入元素，把较小者与当前最小值比较 ，较大者与当前最大值比较（每对元素需要3次比较） 2021/1/26 7 MAX-MINIMUM ( A ) 1 if length[A] is odd 2 then min ← A[1]; max ← min; 3 else min ← MIN( A[1], A[2] ), max ← MAX( A[1], A[2] ); 4 i ++; 5 while i ≤ length[A] 6 min ← MIN( MIN(A[i], A[i+1]), min ) 7 max ← MAX( MAX(A[i], A[i+1]), max ) 8 i ← i+2; 9 end 10 return min, max

最小值和最大值 》如何设定当前最小值和最大值的初始值:依赖于n的奇偶性 如果n是奇数,将最小值和最大值都设为第一个元素的值; 如果n是偶数,就对前两个元素做一次比较,以决定最小值和最大值 的初始值。 总的比较次数: 口如果n是奇数,那么总共做了3n/2次比较 口如果n是偶数,总共做了3n/2-2次比较。 时间复杂度为:O(m) 2021/1/26

最小值和最大值 ➢ 如何设定当前最小值和最大值的初始值：依赖于n的奇偶性 ➢ 如果n是奇数，将最小值和最大值都设为第一个元素的值； ➢ 如果n是偶数，就对前两个元素做一次比较，以决定最小值和最大值 的初始值。 ➢ 总的比较次数：  如果n是奇数，那么总共做了 次比较  如果n是偶数，总共做了 次比较。 2021/1/26 8 3n / 2 3n / 2 − 2 时间复杂度为：O(n)

第七讲顺序统计学 内容提要 口最小值和最大值 口以期望线性时间做选择 口最坏情况线性时间的选择 2021/1/26

2021/1/26 9 第七讲 顺序统计学 内容提要：  最小值和最大值  以期望线性时间做选择  最坏情况线性时间的选择

以期望线性时间做选择 口基本思想:采用分治策略,借鉴快速排序的随机划分法,对输入 数组进行递归划分,但是只处理划分的一边 RANDOMIZED-SELECT(A, P, r,i) P ∥临界问题处理 then return Alp 3q← RANDOMIZED-PARTITION(A,P,r)进行划分,返回划分元下标 4k←q-p+1 ∥k=rank(A[qD)inAp,,r,返回划分元的序号 5 if i=k then return Algl: 7 else if i<k 8 then return RANDOMIZED-SELECT(A, P,g-1,i) else 10 return RANDOMIZED-SELECT( A, 9+1, r,i-k) 2021/1/26

以期望线性时间做选择  基本思想：采用分治策略，借鉴快速排序的随机划分法，对输入 数组进行递归划分，但是只处理划分的一边。 2021/1/26 10 RANDOMIZED-SELECT ( A, p, r, i ) 1 if p = r // 临界问题处理 2 then return A[p] 3 q ← RANDOMIZED-PARTITION( A, p, r ) //进行划分，返回划分元下标 4 k ← q – p + 1 // k=rank(A[q]) in A[p,…,r], 返回划分元的序号 5 if i = k 6 then return A[q]; 7 else if i < k 8 then return RANDOMIZED-SELECT ( A, p, q - 1, i ) 9 else 10 return RANDOMIZED-SELECT( A, q+1, r, i – k )

以期望线性时间做选择 k oA[q] ≥A[q i<k Alq oAq 是所求 ≥A[q] 在此找第i大的元素 在此找第i-大的元素 2021/1/26

以期望线性时间做选择 2021/1/26 11