選択問題
k番目の大きさの要素
• 下記の８つあるデータの中で３番目の大きさ
の要素とは何か？
１，１，２，２，２，３，３，４
– 答え ３ （１，２，３，４の４種類のうちの３番目）
– 答え ２ （左から見て３番目）
k番目の大きさの要素
• k番目の大きさの要素がmであるとは
– （１） mはa1, a2, …, anの中のどれか
– （２）
|{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より真に大きい数 ⇒ 水色の領域
６
９
２
１１
５
１
３
２１
７
１０
１２
４
１４
１３
８
１９
２９
２４
１５
１６
１７
２０
２２
２５
２８
３４
３７
１８
３３
２３
２７
３１
３０
３５
３９
４１
２６
４５
４０
３２
３６
３８
４３
４２
４４
疑中央値mを選ぶ方法
疑中央値より小さい要
A[1..n]を5個の要素からなるグループに分ける; 疑中央値より大きい要
5個の要素からなるグループをソートする;
Mを5個の要素からなるグループの中央値の集合とする;
m := l-select(M,[M/2]);
桃色の領域 ⇒ 22以上の数
素 
3
n
4
3
素  n
4
22より真に小さい数 ⇒ 水色の領域
６
９
２
１１
５
１
３
２１
７
１０
１２
４
１４
１３
８
１９
２９
２４
１５
１６
１７
２０
２２
２５
２８
３４
３７
１８
３３
２３
２７
３１
３０
３５
３９
４１
２６
４５
４０
３２
３６
３８
４３
４２
４４
最悪処理時間はO(n)
• 再起方程式を立てる
procedure l-select(A[1..n],k);
if n<50 then A[1..n]を直接ソートして終了
• Ｔ(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を出力
• Ｔ(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)
• 再起方程式を立てる
• Ｔ(n)：データ数がnのときの処理時間
– Ｔ(n)≦cn
(n≦49)
– Ｔ(n)≦Ｔ(n/5) ＋Ｔ(3n/4)＋cn(n≧50)
• Ｔ(n)≦20cnを帰納法で証明
Ｔ(n) ≦ Ｔ(n/5) ＋Ｔ(3n/4) ＋ cn
≦ 20c(n/5)＋20c(3n/4)＋ cn
＝ 4cn
＋ 15cn
＋ cn
＝ 20cn