選択問題
k番目の大きさの要素
• 下記の8つあるデータの中で3番目の大きさ
の要素とは何か?
1,1,2,2,2,3,3,4
– 答え 3 (1,2,3,4の4種類のうちの3番目)
– 答え 2 (左から見て3番目)
k番目の大きさの要素
• k番目の大きさの要素がmであるとは
– (1) mはa1, a2, …, anの中のどれか
– (2)
|{i ∈{1,2,…,n}| ai < m}| < k
k ≦ |{i ∈{1,2,…,n}| ai ≦ m}|
かつ
k=3, m=2
1
1
2
k
2
2
3
3
4
k番目の大きさの要素を求める処理時間
• 素朴な方法
– ソートしてk番目の要素を選ぶ
⇒ O(n log n)時間かかる
• O(n)時間で可能か?
– P82 手続き select
– P84 手続き l-select
平均処理時間がO(n)
最悪処理時間がO(n)
平均処理時間がO(n)のアルゴリズム
procedure select(A[1..n],k);
if nが小さい then A[1..n]を直接ソートして終了
p:= A[1..n]からランダムに選ぶ;
u:=|{i ∈{1,…,n}|A[i] < p}|;
v:=|{i ∈{1,…,n}|A[i] ≦ p}|;
case (k ≦ u)
select(U[1..u],k);
case (u < k ≦ v)
要素としてpを出力
case (v < k)
select(V[1..n-v],k -v);
u
k
U
k
pppppp pp
u
k
v
n -v
k -v
V
k
|U|, |V|の期待値≦3n/4
• E(n,k):再起呼出しでのUまたはVの大きさの
期待値
• 要素に重複が無い場合を考えれば十分
• i:ランダムに選んだ要素
• E(n,k)
≦(∑ki=1 (n-i) + ∑ni=k+1 (i-1) )/n
≦ 3n/4
i -1
i -1
i -1
i -1 n-i
n-i
n-i
n-i
1
i
i
i
i
k
i
i
i
i
n
i
平均処理時間はO(n)
• O(n+(3/4) n +(3/4)2n +・ ・ ・)=O(n)
n
(3/4)n
・
・
・
(3/4)2n
(3/4)3n
selectを改良してl-selectを導く
O(n)時間で可能か?
– P82 手続き select
– P84 手続き l-select
平均処理時間がO(n)
最悪処理時間がO(n)
如何にしてアルゴリズムを改良するか?
疑中央値より小さい要
procedure select(A[1..n],k);
疑中央値より大きい要
if nが小さい then A[1..n]を直接ソートして終了
疑中央値 p:= A[1..n]からランダムに選ぶ;
u:=|{i ∈{1,…,n}|A[i] < p}|;
v:=|{i ∈{1,…,n}|A[i] ≦ p}|;
case (k ≦ u)
select(U[1..u],k);
case (u < k ≦ v)
要素としてpを出力
case (v < k)
select(V[1..n-v],k -v);
素 
3
n
4
3
素  n
4
|U|, |V|≦3n/4となるような疑中央値を選べばよい
U  疑中央値より小さい要
V  疑中央値より大きい要
素 
3
n
4
3
素  n
4
疑中央値mを選ぶ方法
疑中央値より小さい要
A[1..n]を5個の要素からなるグループに分ける; 疑中央値より大きい要
5個の要素からなるグループをソートする;
Mを5個の要素からなるグループの中央値の集合とする;
m := l-select(M,[M/2]); ←再帰的に処理
桃色の領域 ⇒ 22以下の数
素 
3
n
4
3
素  n
4
22より真に大きい数 ⇒ 水色の領域
6
9
2
11
5
1
3
21
7
10
12
4
14
13
8
19
29
24
15
16
17
20
22
25
28
34
37
18
33
23
27
31
30
35
39
41
26
45
40
32
36
38
43
42
44
疑中央値mを選ぶ方法
疑中央値より小さい要
A[1..n]を5個の要素からなるグループに分ける; 疑中央値より大きい要
5個の要素からなるグループをソートする;
Mを5個の要素からなるグループの中央値の集合とする;
m := l-select(M,[M/2]);
桃色の領域 ⇒ 22以上の数
素 
3
n
4
3
素  n
4
22より真に小さい数 ⇒ 水色の領域
6
9
2
11
5
1
3
21
7
10
12
4
14
13
8
19
29
24
15
16
17
20
22
25
28
34
37
18
33
23
27
31
30
35
39
41
26
45
40
32
36
38
43
42
44
最悪処理時間はO(n)
• 再起方程式を立てる
procedure l-select(A[1..n],k);
if n<50 then A[1..n]を直接ソートして終了
• T(n):データ数がnのときの処理時間
m:= l-select(M,[M/2]);
T (n)  cn
(n  49)
u:=|{i ∈{1,…,n}|A[i] < p}|;
n
 3n 
v:=|{i ∈{1,…,n}|A[i] ≦ p}|;
T (n)  T    T    cn (n  50)
5
 4
case (k≦u)
l-select(U[1..u],k);
case (u<k≦v) pを出力
• T(n)≦20cnを帰納法で証明
case (v<k)
l-select(V[1..n-v],k -v);
n
 3n 
T (n)  T    T    cn
5
 4
n
 3n 
 20c   20c   cn
5
 4

4cn

15cn
 cn
 20cn
ここからは部品
•
•
•
•
E(n,k):再起呼出しでのUまたはVの大きさの期待値
要素に重複が無い場合を考えれば十分
i:ランダムに選んだ要素
i=v=u +1
– case (k ≦ u) → (k<i)
U[1..u]=U[1.. i-1],.
– case (u < k ≦ v) → (k=i) 要素としてpを出力
– case (v n-i]
i -1
n-i
i
最悪処理時間はO(n)
• 再起方程式を立てる
• T(n):データ数がnのときの処理時間
– T(n)≦cn
(n≦49)
– T(n)≦T(n/5) +T(3n/4)+cn(n≧50)
• T(n)≦20cnを帰納法で証明
T(n) ≦ T(n/5) +T(3n/4) + cn
≦ 20c(n/5)+20c(3n/4)+ cn
= 4cn
+ 15cn
+ cn
= 20cn
ダウンロード

Document