《算法导论》第9章:顺序统计、中值
本章主要解决的问题:求数列中第i小的元素
一、排序+下标定位【最坏情况Θ(n*lgn)】
二、随机化分治算法【平均情况Θ(n)】
算法步骤
1.随机选择主元
2.线性时间内以主元划分为两部分,左半部分小于主元,右半部分大于主元。设主元的下标为k。
3.根据情况选择:
if k == i:直接返回A[k]
if k > i:递归最半部分找第i小的数
if k < i:递归右半部分找第i-k小的数
初步分析(假设所有元素都不相同)
精确分析(平均情况)
其中Xk是指示器随机变量{0,1}:
再使用代换法:
代码实现(C++)
#include <iostream>
#include <cstdlib>
using namespace std;
int randomized_partition(int* a, int low, int high)
{
int i = low - 1;
int j = rand() % (high - low + 1) + low;
swap(a[high], a[j]); //a[high] is the pivot
for(int j = low; j < high; ++j)
if(a[j] <= a[high])
swap(a[++i], a[j]);
swap(a[++i], a[high]);
return i;
}
int randomized_select(int* a, int p, int r, int i)
{
if(p == r) return a[p];
int q = randomized_partition(a, p, r);
int k = q - p + 1; //a[q] is the k-th smaller element in array a
if(i == k) return a[q];
else if(i < k) return randomized_select(a, p, q - 1, i);
else return randomized_select(a, q + 1, r, i - k);
}
int main()
{
int a[9] = {3, 5, 7, 9, 8, 6, 1, 2, 4};
cout << randomized_select(a, 0, 9, 5);
return 0;
}
三、选择算法SELECT【最坏情况Θ(n)】
算法步骤
(1)将输入数组的n个元素划分为floor(n/5)组,每组5个元素,且至多只有一组由剩下的n%5个元素组成;
(2)寻找这ceil(n/5)组中每一组的中位数,首先对每组元素进行插入排序,然后确定每组有序元素的中位数;
(3)对第2步中找出的ceil(n/5)个中位数,递归调用SELECT以找出其中位数x(如果有偶数个中位数,约定x是较小的中位数);
(4)利用PARTIONX,按中位数的中位数x对输入数组进行划分。让k比划分的低区中的元素多1,因此x是第k小的元素,并且有n-k个元素在高区。
(5)如果i=k,则返回x。如果i<k,则在低区递归调用SELECT来找出第i小的元素;如果i>k,则在高区递归调用SELECT找出第i-k小的元素。
算法分析
①寻找ceil(n/5)个中位数:Θ(n)
②递归计算ceil(n/5)个中位数的中位数m:T(n/5)
③至少右3n/10个数小于m,因此划分后的子问题规模:T(7n/10)
因此:T(n) = T(7n/10) + T(n/5) + Θ(n)
用代入法可证明:T(n) = Θ(n)
Exercises 9.3-8
Let X[1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y.
解: int findMedian( X[1..n], Y[1..n]) // X 和 Y均为n个以排序的数组
在 X,Y中取中位数,分别为m、n -------- O(1)
if m==n:return m
else if m<n:有floor(n/2)个数小于m,floor(n/2)个数大约n。中位数一定在m-n的区间上。
else if m>n:类似上面
else return findMedian(X[floor(n/2)+1..n],Y[1..floor(n/2)])
T(n) = T(n/2)+O(1)
由master定理,可知复杂度为O(lgn)