第七讲顺序统计学 内容提要 口最小值和最大值 口以期望线性时间做选择 口最坏情况线性时间的选择 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)