Download presentation
Presentation is loading. Please wait.
Published byYuliani Gunardi Modified 5年之前
1
主讲人: 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2012 ,USTC
算法基础 主讲人: 吕敏 { } Spring ,USTC
2
第七讲 顺序统计学 内容提要: 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择 2019/7/24
3
问题描述 在一个由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
4
问题描述 选择问题可以在O(nlgn)时间内解决: 用堆排序或合并排序对输入数据进行排序 再在输出数组中标出第i个元素即可。
还有其他更快的算法。
5
第七讲 顺序统计学 内容提要: 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择 2019/7/24
6
最小值和最大值 最小/最大值:进行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
7
最小值和最大值 同时找最小值和最大值 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
8
最小值和最大值 如何设定当前最小值和最大值的初始值:依赖于n的奇偶性 总的比较次数: 如果n是奇数,那么总共做了 次比较
时间复杂度为:O(n) 2019/7/24
9
第七讲 顺序统计学 内容提要: 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择 2019/7/24
10
以期望线性时间做选择 基本思想:采用分治策略,借鉴快速排序的随机划分法,对输入数组进行递归划分,但是只处理划分的一边。
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
11
以期望线性时间做选择 2019/7/24
12
以期望线性时间做选择 时间复杂度分析: 2019/7/24
13
以期望线性时间做选择 2019/7/24
14
以期望线性时间做选择 2019/7/24
15
以期望线性时间做选择 2019/7/24
16
第七讲 顺序统计学 内容提要: 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择 2019/7/24
17
最坏情况线性时间的选择 基本思想:类似RandomizedSelect算法,通过对输入数组进行递归划分来找出所求元素,但是算法保证每次对数组的划分是个好划分 主要步骤: 2019/7/24
18
最坏情况线性时间的选择 2019/7/24
19
最坏情况线性时间的选择 时间复杂度分析: 由上页图示,可知至少有 的元素较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
20
最坏情况线性时间的选择 利用替换法,令T( n ) = O( cn ) 假设n>140时,c>=20a,上式就可以成立!
2019/7/24
21
最坏情况线性时间的选择 2019/7/24
22
谢谢! Q & A 作业: 2019/7/24
Similar presentations