selection problem最小最大Randomized selectSelection in worst-case linear time

ith order statistic: 第i小的元素 median: 中位数

selection problem

input:n个大小不同的数和一个整数i output:第i小的元素

可以先排序，再选择，时间复杂度 O(nlgn)

最小最大

遍历查找

#include <iostream> using namespace std; int minimum(int * array, int size) { int min = array[0]; for(int i = 1; i < size; i++) if(min > array[i]) min = array[i]; return min; } int main() { int array[10] = {21, 4, 2, 5, 9, 10, 6, 12, 32, 15}; int min = minimum(array, 10); cout << "minimum: " << min << endl; } minimum: 2

Randomized select

Randomized-Select(A, p, r, i) if p == r return A[p] q = Randomized-Partition(A, p, r) k = q - p + 1 if i == k return A[q] elseif i < k return Randomized-Select(A, p ,q-1, i) else return Randomized-Select(A, q+1, r, i-k) #include <iostream> #include <stdlib.h> using namespace std; int minimum(int * array, int size) { int min = array[0]; for(int i = 1; i < size; i++) if(min > array[i]) min = array[i]; return min; } void swap(int & a, int & b){int tmp = a;a = b; b = tmp;} int partition(int * array, int p, int r) { int x = array[r]; int i = p - 1; for(int j = p; j <= r-1; j++) { if(array[j] <= x) { i++; swap(array[i], array[j]); } } swap(array[i + 1], array[r]); return i + 1; } /* RandomizedPartition(A, p, r) i = Random(p, r) exchange A[r] with A[i] return Partition(A, p, r) */ int randomizedPartition(int * array, int p, int r) { int i = rand() % (r - p) + p; swap(array[r], array[i]); return partition(array, p, r); } int randomizedSelect(int * array, int p, int r, int i) { if(p == r) return array[p]; // q表示第q个 int q; q = randomizedPartition(array, p, r); // k表示q之前的个数 + 1 int k = q - p + 1; // 如果正好是i个 if(i == k) return array[q]; // 大于i个，那在前边选 else if(i < k) return randomizedSelect(array, p, q-1, i); else return randomizedSelect(array, q+1, r, i - k); } int main() { int array[10] = {21, 4, 2, 5, 9, 10, 6, 12, 32, 15}; // int min = minimum(array, 10); // cout << "minimum: " << min << endl; int ith; ith = randomizedSelect(array, 0, 9, 2); cout << "The second is " << ith << endl; }

那么这个算法到底做了什么？ random_partition 随机选择一个数，把所有小于等于它的放在左边，大于它的放在右边。 partition之后，看左边有多少个，不够i个，去右边找 i-左边的个数 个。

那么它的时间复杂度是什么？ 对于一个含 n 个元素的数组，它的时间复杂度是 T(n) ，由于是随机partition，所以返回的用于分界的数是等概率分布的。对于每一个k（ 1≤k≤n ），子数组A[p…q]包含k个元素的概率为 1/n ，因为返回的数是等概率的，恰好返回的数，使得小于等于它的有k个概率是1/n。 也就是说： Xk=I{thesubarrayA[p...q]hasexactlykelements} (成立为1 不成立为0，均值等于概率) E[Xk]=1/n

对于每一次调用 randomized select，接下来是迭代 A[p..q-1]还是A[q+1..r]取决于第i个元素落在哪里。为了得到upper bound，假设总落在数目最多的那一部分里。

当 Xk=1 ，partition后的两个子数组长度分别为 k-1 和 n-k 。所以 T(n)≤∑nk=1Xk∗(T(maxk−1,n−k))+O(n))

取均值

那么怎么证明T(n)的平均是 O(n)呢？ 假设，对于小于一个常数的n，T(n) = O(1)，并且T(n) <= cn，具体见算法导论 CLRS

Selection in worst-case linear time

上面的方法在最坏情况下是 O(n2)

现在来介绍一个最坏是 O(n) 的算法。

SELECT 1. n个元素分为floor(n/5)每组5个，最后一组是n mod 5个 2. 找到每组的中位数 3. partition这些中位数，找到这些中位数的中位数，假设分为k-1和n-k，第k个是x 4. 如果i==k，返回x，否则，递归SELECT，找到第i个元素