2013-10-04 18:31:09Morris
[C/C++][實做] Selection algorithm
Selection Algorithm
算法描述：
問題：給定序列中的找到第 k 小數字。
一般會使用 sorting algorithm 在 O(n logn) 排序後找到 k-th 小數字。
又或者使用一個 heap 維護，在效率 O(n logk) 內找到，但這一算法可以在 O(n) 時間內完成。
算法步驟：
詳細步驟&證明請參考：
http://www.cnblogs.com/hibernate6/archive/2011/04/28/2522298.html
稍微描述一下核心，通常使用 RANDOM-SELECT 也可以達到平均複雜度 O(n)，但這裡要找到最慘情況下可以在 O(n) 的算法，RANDOM-SELECT 類似於 quick sort 的一部分，只要能確保 pivot 盡可能是中位數的話，效率就能在最慘達到 O(n)。
於是這裡設計一個遞迴的操作：
首先，定義函數：
(1) selectionAlgorithm() 回傳指定序列中的第 k 小的索引值
(2) medianOfMedians() 回傳序列的 "近似中位數" 的索引值
由於 selectionAlgorithm() 寫法與 RANDOM-SELECT 的做法一樣，這裡著重於找到近似中位數。
medianOfMedians()：
1. 將數列 5 個數字分一堆，最後一堆少於 5 個，每組找到中位數。
2. 對於這 5 個數字使用 "插入排序" 得到中位數，假設這個操作 O(1)。
3. 得到所有中位數後，調用 selectionAlgorithm 確切找到中位數們的中位數。
selectionAlgoithm()：
1. 增加修改的地方為 pivot 調用 medianOfMedians() 得到。
由於 "近似中位數" 的效用，保證劃分的位置可以在 [3/10 * n, 7/10 * n] 之間。
換而言之，如果將 medianOfMedians() 放回 selectionAlgorithm()：
得到遞迴 T(n) = T(n/5) + T(7n/10+6) + O(n)
其中 T(n/5) 是 medianOfMedians() 調用 selectionAlgorithm()
T(7n/10) 則是在最慘的情況下，繼續在 7n/10 個數字下遞歸。
證明：O(n)，將使用數學歸納法證明。
假設 T(n) <= cn, c > 0 是常數
規定 T(n) = O(1), when n < 140
T(n) <= T(n/5) + T(7n/10+6) + O(n)
=> T(n) <= c(n/5+1) + c(7n/10+6) + an
=> T(n) <= 9cn/10 + 7c + an
=> T(n) <= cn + (-cn/10 + 7c + an)
解 (-cn/10 + 7c + an) <= 0，
=> c >= 10a(n / (n-70) )
=> for n >= 140, n/(n-70) >= 2, c >= 20a 即可。
因此得到最慘情況 O(n)。
範例輸入：
10 0
14 11 25 17 17 14 14 3 19 12
10 8
4 1 4 9 22 25 10 19 6 23
10 9
16 6 9 20 15 21 5 21 6 26
範例輸出：
3
23
26
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#define debug 0
using namespace std;
int selectionAlgorithm(int[], int, int, int);
int medianOfMedians(int[], int, int);
int selectionAlgorithm(int a[], int l, int r, int k) {
/**
* k = 0, 1, 2, ...
* return k-th smallest value.
*/
if(r-l+1 <= 5) {// insert sort.
int i, j, v;
for(i = l+1; i <= r; i++) {
v = a[i], j = i;
while(j-1 >= l && a[j-1] > v)
a[j] = a[j-1], j--;
a[j] = v;
}
return l+k;
}
//printf("%d %d\n", l, r);
int pivot = medianOfMedians(a, l, r);
// partition begin.
swap(a[l], a[pivot]);
int i, j, t = a[l];
for(i = l, j = l+1; j <= r; j++) {
if(a[j] <= t)
i++, swap(a[i], a[j]);
}
swap(a[l], a[i]);
// partition end.
int position = i;
#if debug == 1
printf("pivot = %d ", t);
printf("[");
for(i = l; i <= position; i++)
printf("%d ", a[i]);
printf("]");
printf("[");
for(i = position+1; i <= r; i++)
printf("%d ", a[i]);
printf("]\n");
#endif
if(position-l == k) return position;
if(position-l < k)
return selectionAlgorithm(a, position+1, r, k-(position-l+1));
else
return selectionAlgorithm(a, l, position, k);
}
int medianOfMedians(int a[], int l, int r) {
int numMedians = (r-l+4)/5;
int i, subl, subr;
int medianIdx;
for(i = 0; i < numMedians; i++) {
subl = l + i*5;
subr = subl + 4;
if(subr > r) subr = r;
medianIdx = selectionAlgorithm(a, subl, subr, (subr-subl)/2);
swap(a[l+i], a[medianIdx]);
}
//printf("median %d %d\n", l, r);
return selectionAlgorithm(a, l, l+numMedians, numMedians/2);
}
int a[1000005];
int main() {
clock_t st, ed;
st = clock();
//srand(time(NULL));
freopen("in.txt","r+t",stdin);
freopen("out.txt","w+t",stdout);
int n, m;
int i;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
int idx = selectionAlgorithm(a, 0, n-1, m);
printf("%d\n", a[idx]);
}
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}
算法描述：
問題：給定序列中的找到第 k 小數字。
一般會使用 sorting algorithm 在 O(n logn) 排序後找到 k-th 小數字。
又或者使用一個 heap 維護，在效率 O(n logk) 內找到，但這一算法可以在 O(n) 時間內完成。
算法步驟：
詳細步驟&證明請參考：
http://www.cnblogs.com/hibernate6/archive/2011/04/28/2522298.html
稍微描述一下核心，通常使用 RANDOM-SELECT 也可以達到平均複雜度 O(n)，但這裡要找到最慘情況下可以在 O(n) 的算法，RANDOM-SELECT 類似於 quick sort 的一部分，只要能確保 pivot 盡可能是中位數的話，效率就能在最慘達到 O(n)。
於是這裡設計一個遞迴的操作：
首先，定義函數：
(1) selectionAlgorithm() 回傳指定序列中的第 k 小的索引值
(2) medianOfMedians() 回傳序列的 "近似中位數" 的索引值
由於 selectionAlgorithm() 寫法與 RANDOM-SELECT 的做法一樣，這裡著重於找到近似中位數。
medianOfMedians()：
1. 將數列 5 個數字分一堆，最後一堆少於 5 個，每組找到中位數。
2. 對於這 5 個數字使用 "插入排序" 得到中位數，假設這個操作 O(1)。
3. 得到所有中位數後，調用 selectionAlgorithm 確切找到中位數們的中位數。
selectionAlgoithm()：
1. 增加修改的地方為 pivot 調用 medianOfMedians() 得到。
由於 "近似中位數" 的效用，保證劃分的位置可以在 [3/10 * n, 7/10 * n] 之間。
換而言之，如果將 medianOfMedians() 放回 selectionAlgorithm()：
得到遞迴 T(n) = T(n/5) + T(7n/10+6) + O(n)
其中 T(n/5) 是 medianOfMedians() 調用 selectionAlgorithm()
T(7n/10) 則是在最慘的情況下，繼續在 7n/10 個數字下遞歸。
證明：O(n)，將使用數學歸納法證明。
假設 T(n) <= cn, c > 0 是常數
規定 T(n) = O(1), when n < 140
T(n) <= T(n/5) + T(7n/10+6) + O(n)
=> T(n) <= c(n/5+1) + c(7n/10+6) + an
=> T(n) <= 9cn/10 + 7c + an
=> T(n) <= cn + (-cn/10 + 7c + an)
解 (-cn/10 + 7c + an) <= 0，
=> c >= 10a(n / (n-70) )
=> for n >= 140, n/(n-70) >= 2, c >= 20a 即可。
因此得到最慘情況 O(n)。
範例輸入：
10 0
14 11 25 17 17 14 14 3 19 12
10 8
4 1 4 9 22 25 10 19 6 23
10 9
16 6 9 20 15 21 5 21 6 26
範例輸出：
3
23
26
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#define debug 0
using namespace std;
int selectionAlgorithm(int[], int, int, int);
int medianOfMedians(int[], int, int);
int selectionAlgorithm(int a[], int l, int r, int k) {
/**
* k = 0, 1, 2, ...
* return k-th smallest value.
*/
if(r-l+1 <= 5) {// insert sort.
int i, j, v;
for(i = l+1; i <= r; i++) {
v = a[i], j = i;
while(j-1 >= l && a[j-1] > v)
a[j] = a[j-1], j--;
a[j] = v;
}
return l+k;
}
//printf("%d %d\n", l, r);
int pivot = medianOfMedians(a, l, r);
// partition begin.
swap(a[l], a[pivot]);
int i, j, t = a[l];
for(i = l, j = l+1; j <= r; j++) {
if(a[j] <= t)
i++, swap(a[i], a[j]);
}
swap(a[l], a[i]);
// partition end.
int position = i;
#if debug == 1
printf("pivot = %d ", t);
printf("[");
for(i = l; i <= position; i++)
printf("%d ", a[i]);
printf("]");
printf("[");
for(i = position+1; i <= r; i++)
printf("%d ", a[i]);
printf("]\n");
#endif
if(position-l == k) return position;
if(position-l < k)
return selectionAlgorithm(a, position+1, r, k-(position-l+1));
else
return selectionAlgorithm(a, l, position, k);
}
int medianOfMedians(int a[], int l, int r) {
int numMedians = (r-l+4)/5;
int i, subl, subr;
int medianIdx;
for(i = 0; i < numMedians; i++) {
subl = l + i*5;
subr = subl + 4;
if(subr > r) subr = r;
medianIdx = selectionAlgorithm(a, subl, subr, (subr-subl)/2);
swap(a[l+i], a[medianIdx]);
}
//printf("median %d %d\n", l, r);
return selectionAlgorithm(a, l, l+numMedians, numMedians/2);
}
int a[1000005];
int main() {
clock_t st, ed;
st = clock();
//srand(time(NULL));
freopen("in.txt","r+t",stdin);
freopen("out.txt","w+t",stdout);
int n, m;
int i;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
int idx = selectionAlgorithm(a, 0, n-1, m);
printf("%d\n", a[idx]);
}
ed = clock();
printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
return 0;
}
上一篇：CountSort + SA
你好，不好意思我想請問一下
在medianOfMedians function中
int numMedians = (r-l)/5;
為什麼不是ceil((double)(r-l)/5)) ??
那假如我傳size為10個大小的陣列進去
那median的個數不是應該要有5個嗎??
可是如果帶入(r-l)/5
算出來只會有1個median
我對此有疑問
能麻煩回gmail信給我嗎 ??
版主回應
你說的沒有錯，這裡是我寫錯了，修正為 int numMedians = (r-l+4)/5;
2014-04-12 14:47:51
我的信箱為 he01350446@gmail.com