N i - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第11回
10. 中央値と順序統計量
• n 要素の集合の i 番目の順序統計量 (order
statistic): その集合で i 番目に小さい要素
• 最小値 (minimum): i = 1
• 最大値 (maximum): i = n
• 中央値 (median):
– n が奇数のとき i = (n+1)/2
– n が偶数のとき i  (n  1) / 2とi  (n  1) / 2
– いずれの場合も i  (n  1) / 2
2
選択問題 (selection problem)
• 入力: n 個の異なる数の集合 A, 整数 i (1  i  n)
• 出力: A 中のちょうど i 1 個の他の要素より大きい
要素 x  A
• 選択問題は O(n lg n) 時間で解ける
– A の要素をソートする
– 出力配列の i 番目の要素を返す
• 選択問題は O(n) 時間で解ける
3
10.2 平均線形時間の選択法
• 順序統計量は (n) 時間で求まるが複雑
• まず，平均的に O(n) 時間のアルゴリズムを考える
data RANDOMIZED_SELECT(data *A, int p, int r, int i)
// A[p..r] の中で i 番目に小さい要素を返す
{
int q, k;
if (p == r) return A[p];
q = RANDOMIZED_PARTITION(A,p,r); // q: 分割の位置
k = q – p + 1;
// k: 左部分の要素数
if (i <= k) return RANDOMIZED_SELECT(A,p,q,i);
else
return RANDOMIZED_SELECT(A,q+1,r,ik);
4
}
• q = RANDOMIZED_PARTITION(A,p,r);の実行後
– 2つの空でない部分配列 A[p..q], A[q+1..r] に分かれる
– 左側の各要素は右側よりも小さい
– k = q – p + 1; は左側の要素数
• i  k ならば i 番目の要素は左側の i 番目
• i  k ならば i 番目の要素は右側の i  k 番目
• 部分配列のサイズが 1 になるまで繰り返す
5
平均実行時間の上界
• T(n): n 要素の集合での選択問題の平均時間
• 分割の左側のサイズが
– 1 になる確率 = 2/n
– i になる確率 = 1/n (i = 2,3,...,n1)
• T(n) は単調増加と仮定する
n 1
1

T n    T max 1, n  1   T max k , n  k   O(n)
n
k 1

n 1

1
  T n  1  2  T k   O(n)
n
k  n / 2 

2 n 1

T k   O(n)

n k  n / 2 
6
• RANDOMIZED_SELECTの最悪実行時間は(n2)
よって 1/n T(n1) = O(n)
• T(n)  cn と仮定すると
2 n 1
T n  
 ck  dn
n k  n / 2 
n / 2 1 
2c  n 1
   k   k   dn
n  k 1
k 1 
2c  1
1   n   n  
  n  1n      1     dn
n 2
2   2   2  
cn n
 cn  1    1  dn
n2 2
1
3
 c n    dn
2
4
if c(n / 4  1 / 2)  dn 
 cn
7
10.3 最悪線形時間の
選択アルゴリズム
アルゴリズム SELECT: i 番目に小さい要素を返す
1. 入力配列の n 要素をグループに分割
–
–
5要素のグループ n/5 個
n mod 5 要素のグループ高々1個
2. n/5 個の各グループを(挿入ソート等で)ソートし，
それぞれの中央値を求める
3. SELECTを再帰的に用いてステップ2で求めた
n/5 個の値の中央値 x を求める
8
4. PARTITIONを修正したものを用い，入力配列を x
によって分割する．左側の要素数を k とする.
5. i  k ならば，左側で i 番目に小さい要素を再帰
的に見つける．
i  k ならば，右側で ik 番目に小さい要素を再帰
的に見つける．
9
SELECTの実行時間の解析
• 分割に用いた x より大きい要素数の下界を求める
• ステップ 2 で求めた中央値の少なくとも半分は x
(中央値の中央値) 以上
• 中央値が x 以上のグループには，x 以上の値が 3
個以上ある
• x 以上となる要素数は少なくとも
  1  n    3n
3      2  
6
  2  5    10
10
• 同様に，x 以下となる要素数も少なくとも 3n/106
• ステップ 5 で再帰的に呼ばれる SELECT の部分
問題のサイズは高々 7n/10+6
• ステップ 1,4: O(n) 時間
• ステップ 2: 5 要素のソートを n/5 回⇒ O(n)時間
• ステップ 3: T(n/5) 時間
(1)
n  80のとき

T ( n)  
T n / 5  T 7n / 10  6  On  n  80のとき
11
• n  80 に対して T(n)  cn と仮定する.
c を十分大きくとれば
T (n)  c n / 5  c7n / 10  6  On 
 cn / 5  7cn / 10  6c  On 
 9cn / 10  7c  On 
 cn
• よって，SELECTの最悪実行時間は線形
• これは比較しか用いていない
12
• クイックソートの pivot として厳密な中央値を
用いれば，最悪計算量が O(n log n) になる
• ただし，SELECTが複雑なので実行速度は
速くない
• また，in-placeではなくなる
13
9. 線形時間のソーティング
• 今までのソートアルゴリズム
– 入力要素の比較のみに基づく
– 比較ソート (comparison sort) と呼ぶ
– 例：マージソート，ヒープソート，クイックソート
– 計算量：(n lg n)
• この節でのソートアルゴリズム
– 比較以外の演算を用いる
– 例：計数ソート，基数ソート，バケットソート
– 計算量：O(n) (線形時間)
14
9.2 計数ソート (counting sort)
• n 個の各入力要素が 1 から k の範囲の整数で
あると仮定 (k: ある整数)
• k = O(n) のとき，計数ソートは O(n) 時間
• 基本的なアイデア
– 各入力要素 x に対し，x より小さい要素の数を決定
– その要素数から x の出力配列での位置が決まる
– 例： x より小さい数が17個 ⇒ x の出力位置は18
– 複数の要素が同じ値を持つ場合に対応する必要あり
15
計数ソートのプログラム
• A[1..n], B[1..n]: 入出力配列
• C[1..k]: 補助的な配列
void COUNTING_SORT(int *A, int *B, int *C, int n, int k)
{
int i,j;
for (i=1; i<=k; i++) C[i] = 0;
for (j=1; j<=n; j++) C[A[j]] = C[A[j]] + 1;
// C[i] は i に等しい要素の個数を含む
for (i=2; i<=k; i++) C[i] = C[i] + C[i-1];
// C[i] は i 以下の要素の個数を含む
for (j=n; j>=1; j--) {
B[C[A[j]]] = A[j];
C[A[j]] = C[A[j]] - 1;
}
}
16
1 2 3 4 5 6 7 8
A 3 6 4 1 3 4 1 4
1 2 3 4 5 6
C 2 0 2 3 0 1
1 2 3 4 5 6
C 120 2 423 7546 7 87
1 2 3 4 5 6 7 8
B 1 1 3 3 4 4 4 6
for (j=1; j<=n; j++) C[A[j]] = C[A[j]] + 1;
// C[i] は i に等しい要素の個数を含む
for (i=2; i<=k; i++) C[i] = C[i] + C[i-1];
// C[i] は i 以下の要素の個数を含む
for (j=n; j>=1; j--) {
B[C[A[j]]] = A[j]; // A[j]以下がC[A[j]]個
C[A[j]] = C[A[j]] - 1;
}
17
計数ソートの計算時間
•
•
•
•
C の初期化: O(k) 時間
頻度の計算: O(n) 時間
累積頻度の計算: O(k) 時間
出力配列の計算: O(n) 時間
• 全体で O(k + n) 時間
• k = O(n) のとき，全体で O(n) 時間
• 比較ソートの下限 (n lg n) を下回る
18
安定なソート
• 同一の値は入力と出力で同じ順序になる
• 付属データをキーに従ってソートする場合に重要
1 2 3 4 5 6 7 8
A 3 6 4 1 3 4 1 4
B 1 1 3 3 4 4 4 6
19
9.3 基数ソート (radix sort)
• 数の集合をある桁に従って分割する機械がある
• この機械を用いて d 桁の数 n 個をソートしたい
329
457
657
839
436
720
355
329
355
457
436
657
720
839
20
• まず最上位桁でソート (分割) し，それぞれを
再帰的にソートすることを考える
• 大量の部分問題が生成される
• 解：最下位桁からソートする⇒基数ソート
– まず最下位桁に従ってソート
– 次に下から2桁目に従ってソート
– d 桁目まで繰り返す
21
329
457
657
839
436
720
355
720
355
436
457
657
329
839
720
329
436
839
355
457
657
329
355
436
457
657
720
839
基数ソートでは各桁のソートは安定である必要がある
22
基数ソートの擬似コード
RADIX_SORT(A,d)
1. for (i=1; i<=d; i++)
2. 安定ソートを用いて i 桁目に関して配列をソー
ト
実行時間の解析
• 各桁が 1 から k の範囲として計数ソートを使用
• d パスあるので (d(n+k)) 時間
23
• d が定数で k = O(n) ならば，全体で O(n) 時間
• n = 100万個の64ビットの数をソートするとする
• 比較ソートでは1つの数あたりほぼ lg n = 20 回の
操作が必要となる
• 基数ソートでは，これらの数を4桁の216進数と思う
と，4回のパスでソートできる
• 計数ソートを用いる基数ソートはin-placeではない
– メモリが高価な場合はクイックソートなどの方が良い
24
9.4 バケットソート (bucket sort)
• 入力： [0,1) の実数 n 個．一様分布と仮定
• アイデア
– 区間を n 個の同じサイズの部分区間 (バケット) に分割
– n 個の入力をバケットに分配
– 各バケットを独立にソート
0.15
0.51 0.45 0.75 0.80
[0,.2) [.2,.4) [.4,.6) [.6,.8) [.8,1.0)
25
バケットソートの動作
A[1..n]: 入力配列
B[0..n1]: バケット (リストの配列)
BUCKET_SORT(A,n)
1. for (i = 1; i  n; i++)
2.
A[i] をリスト B[nA[i]] に挿入する
3. for (i = 0; i  n1; i++)
4. リスト B[i] を挿入ソートでソートする
5. リスト B[0], B[1],...,B[n1] を順に連接する
26
1
2
3
4
5
6
7
8
9
10
A
.78
.17
.39
.26
.72
.94
.21
.12
.23
.68
.12
B
0
1
2
3
.12
.17
.21
.26
.23
.39
.17
.23
.26
.21
.26
4
5
6
7
.68
.72
.78
.78
8
9
.94
.17 各リストを挿入ソートでソート
.21
.23
.26
.39
.68
.72
.78
.94
27
アルゴリズムの正当性
• A[i] と A[j] が同じバケットに入る場合
– 各バケットは挿入ソートでソートされるのでOK
• A[i] と A[j] が異なるバケットに入る場合
– バケット B[i’], B[j’] (i’ j’)に入るとする
– アルゴリズムの最後で B のリストは結合される
– B[i’] の要素は B[j’] の要素よりも前に現れる
– よって，出力中で A[i] は A[j] よりも前に現れる
– つまり， A[i]  A[j] を示せばよい
28
• A[i]  A[j] と仮定して矛盾を導く．
i  nA[i ]
 nA[ j ]
 j
• となり，i’ j’ に矛盾する
29
実行時間の解析
• 挿入ソート以外の部分は O(n) 時間
• Ni: バケット B[i] に入れられる要素数を表す
確率変数
• バケット B[i] の要素をソートするのに必要な
平均時間 = E[O(Ni2)] = O(E[Ni2])
• 全てのバケット中の要素をソートする時間は
n 1
n 1

2
2 
O(E[ N i ])  O  E[ N i ] 

i 0
 i 0

30
確率変数 Ni の分布
•
•
•
•
•
要素数 = バケット数 = n
ある要素が B[i] に入る確率は p = 1/n
Ni = k となる確率は2項分布 B(k;n,p) に従う
E[Ni] = np = 1, Var[Ni] = np(1p) = 11/n
E[Ni2] = Var[Ni] + E2[Ni] = 21/n = (1)
以上より，挿入ソートに必要な時間は O(n)
バケットソートは線形時間で動作する
31

Download Report