Document

第10章中央値と順序統計量
10.1 最大と最小
10.2 平均線形時間の選択法
10.3 最悪線形時間の選択アルゴリズム
第10章中央値と順序統計量
• i番目の順序統計量とは
– ｎ要素の集合のi番目に小さい要素のことである
– 最小値、最大値
– 中央値：
• 奇数ならば、(n+1)/2
• 偶数ならば、大きい中央値 éê n / 2 ùú・小さい中央値 êë n / 2 úû
– 選択問題
• 入力：ｎ個の異なる数の集合Aと整数
• 出力：i番目大きい要素
• 計算量：ヒープソートやマージソートを使ってO(nlgn)で解けるが、
もっと高速のアルゴリズムが存在する
10.1 最大と最小
• 素朴なアルゴリズム
MINIMUM(A)
1. min ← A[1]
2. for i ← 2 to length[A]
3.
do if min > A[i]
4.
then min ← A[i]
5. return min
min
a1
a2
a3
a4
– ｎ-1回の比較して、最小値や最大値を得られる
– 各比較はトーナメントの試合に相当し、優勝者以
外は少なくともn-1回の比較が必要なので、この
アルゴリズムは最良である。
10.1 最大と最小
• 同時に最大と最小を求める
– 素朴なアルゴリズムならば、2（n-1）回の比較
– 3 êë n / 2 úû 回の比較で動作するアルゴリズム
• アイデア：2つの要素を対にして処理する。入力の最初
から2つの要素をお互いに比較し、各2要素毎3回の比
較を単位として小さい方とそれまでの最小値を、大き
い方とそれまでの最大値をそれぞれ比較する。
10.1 最大と最小
–
3 êë n / 2 úû 回の証明
• ｎ＝奇数の場合
min
a1
min
a1
max
a2
max
a2
比較の回数は3[(n -1) / 2]
= 3 êë n / 2 úû
a3
a3
a4
a4
• n=偶数の場合
a5
比較の回数は 1+ 3(n - 2) / 2 = 3n / 2 - 2
< 3 êë n / 2 úû
• つまり、少なくとも 3 êë n / 2 úû 回の比較
min
a1
max
a2
10.2 平均線形時間の選択法
• 選択問題に対して分割統治のアルゴリズム
– アイデア：クイックソートと同様に入力配列を再帰
的に分割して、i番目の大きい・小さい要素がを必
ず一つの部分にあり、分割の一方のみ、その要
素を見つかるまで範囲を小さくする。
– クイックソートのRANDOMIZED-PARTITIONを利用
する確率的アルゴリズムである。
10.2 平均線形時間の選択法
• コード
RANDOMIZED-SELECT(A, p, r, i)
1. if p = r ▹一つの要素しかない場合、その要素を返す
2.
then return A[p]
3. q ← RANDOMIZED-PARTITION(A, p, r) ▹クイックソートの手続きを利用
4. k ← q - p + 1 ▹2つの部分列のいずれか決定するために、ｋを計算する
5. if i <= k ▹再帰的に見つけられる
6.
then return RANDOMIZED-SELECT(A, p, q - 1, i) ▹分割の小さい部分
7. else return RANDOMIZED-SELECT(A, q + 1, r, i - k) ▹分割の大きい部分
8.3節で示されたRANDOMIZED-PARTITIONが確率的なアルゴリズムなので、
RANDOMIZED-SELECTも確率的なアルゴリズムである。
10.2 平均線形時間の選択法
– 計算量
• 常に最大の要素のみ残されるように分割される場合、
2
最小値を見つけるために、 o(n )時間かかる。
• しかしながら、このアルゴリズムは平均的にはうまく動
作し、確率的アルゴリズムなのでどのような入力に対
しても最悪の振る舞いをしない。
10.2 平均線形時間の選択法
• 計算量
n-1
1
T (n) £ (T (max(1,n -1)) + å T (max(k,n - k))) + O(n)
n
k=1
ïì k, k > êë n / 2 úû
max(1,n -1) = n -1& max(k,n - k) = í
ïîn - k, k < éê n / 2 ùú
したがって、
ｎが偶数ならば、和の中には T (éên / 2 ùú),T (éên / 2 ùú +1),...,T (n -1) の各項は２回現れ
ｎが奇数数ならば、和の中には T (éê n / 2 ùú +1),T (éên / 2 ùú + 2),...,T (n -1)の各項は２回、 T (éê n / 2 ùú) １回現れ
なので
n-1
1
T (n) £ (T (n -1) + 2 å T (k )) + O(n)
n
k= éê n/2 ùú
最悪の場合 T (n -1) = O(n 2 ) なので
2 n-1
T (n) = å T (k ) + O(n)
n k= éên/2 ùú
この漸化式は置き換え法によって解くことができる
10.2 平均線形時間の選択法
• 計算量
2 n-1
T (n) £ å ck + O(n)
n k= êën/2 úû
T(n)<=cnを仮定すると
êë n/2 úû-1
ö
2c æ n-1
= ç å k - å k ÷ + O(n)
n è k=1
ø
k=1
=
2c æ 1
1
ö
(n
1)n
(
n
/
2
1)
n
/
2
ê
ú
ê
ú
ë
û
ë
û÷ø + O(n)
çè
n 2
2
2c æ 1
1
ö
(n
1)n
(n
/
2
2)(n
/
2
1)
çè
÷ø + O(n)
n 2
2
c
= (3n 2 / 4 + n / 2 - 2) + O(n) = c(3n / 4 + 1 / 2 - 2 / n) + O(n)
n
£ c(3n / 4 - 1 / 2) + O(n) = cn
£
10.3 最悪線形時間の選択アルゴリズム
• アルゴリズム
– アイデア：入力配列を再帰的に分割する時、必ず
上手な分割を保証するということである。
– ８．１節のクイックソートの決定性の分割アルゴリ
ズムPartitionを用いる。
10.3 最悪線形時間の選択アルゴリズム
• 手続き
1. 入力配列のｎ要素を5要素の êën / 5 úû 個のグルー
プと残りの個からなる高々1個のグループに分
ける。O(ｎ)時間かかる。
10.3 最悪線形時間の選択アルゴリズム
• 手続き
2. 各グループの（高々5個）要素を挿入ソートによってソー
トして、それぞれの中央値をとることによって n/5 個の
中央値を求める。 O(１)のサイズに対する挿入ソートを
O(n)回呼ぶため、 O(ｎ)時間かかる。
10.3 最悪線形時間の選択アルゴリズム
• 手続き
3.
ìO(1),n £ 80
T (n) £ í
SELECTを再帰的にStep2.で見つけた
個の中央値を
T
(
n
/
5
)
+
T
(7n
/10
+ 6) + O(n),n > 80
é
ù
ú
î ê
求める。 SELECTの実行時間がT（ｎ）を仮定すると、Step3.
T ( éê n / 5 ùú)
の実行時間が
10.3 最悪線形時間の選択アルゴリズム
• 手続き
4. 変更されたPARTITIONを用いて入力配列を中央値の中
央値ｘによって分割する。ｋを分割の小さい方の要素数
とする。この時、大きい方にはn-k個の要素がある。
PARTITION がO(ｎ)時間かかる（８．１節）。
10.3 最悪線形時間の選択アルゴリズム
• 手続き
5.
ならば、小さい方にi番目に小さい要素を見つけるよう、
ならば大きい方に対して番目に小さい要素を見つけるようにSelect
を再帰的に用いる。灰色の部分はｘより大きい要素である、その要
æ é 1 é n ù ù ö 3n
素の数が
3ç ê ê ú ú - 2 ÷ ³ - 6
è ê 2 ê 5 ú ú ø 10
したがって最悪の場合、
n-(
3n
7n
- 6) =
+6
10
10
要素に対して再帰的に呼ばれる。
Step5.が T (7n /10 + 6)
10.3 最悪線形時間の選択アルゴリズム
• 次の漸化式を得られる
ìO(1),n £ 80
îT (éê n / 5 ùú) + T (7n /10 + 6) + O(n),n > 80
T (n) £ í
• 80以下の任意の入力に対してはO（1）の時間と仮定すると、置き換え法
によって：
T (n) £ c éê n / 5 ùú + c(7n /10 + 6) + O(n)
£ cn / 5 + c + 7cn /10 + 6c + O(n)
£ 9n /10 + 7c + O(n)
£ cn
よって、
Selectの最悪実行時間は線形である。
以上です。
ありがとうございました！

Download Report