n - Researchmap

算法数理工学
第1回
定兼邦彦
1
目的・成績評価・参考書
• アルゴリズム理論による設計は，大規模なデータを高速で処理
する際に特に有効
• 部品 (データ構造) を組み合わせてプログラムを作るだけでなく，
部品の中身を理解する
•
•
•
•
成績評価は試験とレポート
メール： [email protected]
ホームページ： http://researchmap.jp/sada/
居室: 工学部6号館341
• 参考書：アルゴリズムイントロダクション(近代科学社)など
プログラミング問題集 AIZU ONLINE JUDGE
問題セットの Introduction to Algorithms and Data Structures
http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=ALDS1
2
アルゴリズムの概念
～オーダーと計算量～
・算法 = アルゴリズム (algorithm)
・アルゴリズムの概念
・オーダーの定義と計算量
3
アルゴリズム
• アルゴリズムとは
– 入力 (input): ある値(の集合)
– 出力(output): ある値(の集合)
– 明確に定義された計算手続き
• 明確に定義された計算問題を解くための道具
• 問題の記述とは
– 望むべき入出力関係を指定すること
4
ソーティング問題の形式的定義
• 入力: n 個の数の列〈a1, a2, ..., an〉
• 出力: a’1 a’2  …  a’n であるような入力
列の置換〈a’1, a’2, ..., a’n〉
• 入力例 (具体例, instance)
– 入力〈31, 41, 59, 26, 41,58〉
– 出力〈26, 31, 41, 41, 58, 59〉
5
ソーティング
• 計算機科学における基本的な操作
• 多くのアルゴリズムが開発されている
• 入力例によって優劣が異なる
– ソートすべきデータの数
– どの程度までデータがすでにソートされているか
– 用いる記憶装置の種類 (主記憶, ディスク, テープ)
6
アルゴリズムの正しさ
• アルゴリズムが正しい (correct)
⇒全ての具体例に対して正しい出力とともに停止する
– 与えられた計算問題を解く (solve) という．
• 正しくないアルゴリズム
– ある具体例に対して望ましい答えを出力せずに停止
– ある具体例に対して全く停止しない
• 確率的アルゴリズムも存在
– モンテカルロ法 (高い確率で正しい答えを出す)
• 円周率の計算，素数判定
– ラスベガス法 (高い確率で早く停止する)
• ランダムクイックソート
7
挿入ソート
• 入力: 長さ n の配列 A[0..n-1]
• 出力: ソートされた配列 A[0..n-1]
void INSERTION-SORT(data *A, int n)
{
data key;
int i, j;
for (j=1; j < n; j++) {
key = A[j];
// A[j] をソート列 A[0..j-1] に挿入する
i = j – 1;
while (i >= 0 && A[i] > key) {
A[i+1] = A[i];
i = i -1;
}
A[i+1] = key;
}
}
5
2
4
6
1
3
2
5
4
6
1
3
2
4
5
6
1
3
2
4
5
6
1
3
1
2
4
5
6
3
1
2
3
4
5
6
入力
出力
8
C言語の場合
#include <stdio.h>
#include <stdlib.h>
typedef int data;
void INSERTION_SORT(data *A, int n)
{
data key;
int i, j;
for (j=1; j < n; j++) {
key = A[j];
// A[j] をソート列 A[0..j-1] に挿入する
i = j - 1;
while (i >= 0 && A[i] > key) {
A[i+1] = A[i];
i = i - 1;
}
A[i+1] = key;
}
}
int main(int argc, char *argv[])
{
data A[14] =
{27,17,3,16,13,10,1,5,7,12,4,8,9,0};
int i,n;
n = 14;
INSERTION_SORT(A,n);
for (i=0;i<n;i++) printf("%d ",A[i]);
printf("\n");
}
9
アルゴリズムの解析
• アルゴリズムの実行に必要な資源を予測したい
– メモリ量
– 通信バンド幅, 論理ゲート
– 計算時間
• 解析を行うにはモデルを仮定する必要がある
• RAM (random access machine) モデル
– 命令は1つずつ実行
– どのメモリ番地も一定の時間で読み書き可
10
挿入ソートの解析
• INSERTION-SORTの手続きに要する時間は入
力によって変わる.
• 一般に, プログラムの実行時間は入力のサイズ
の関数で表す.
• 入力サイズの定義
– ソーティング, 離散フーリエ変換など: データ数
– 整数の積の計算など: 入力のビット数
– グラフの問題: グラフの頂点と辺の数
11
実行時間の定義
• 実行される基本的な演算の回数
• プログラムの第 i 行の実行に ci 時間かかるとす
る (ci は定数)
• 注: サブルーチン呼び出しは定数時間ではない
12
void INSERTION-SORT(data *A, int n)
{
data key;
int i, j;
for (j=2; j <= n; j++) {
key = A[j];
// A[j] をソート列 A[1..j-1] に挿入する
i = j – 1;
コスト
回数
c1
c2
n
n-1
c4
n-1
n
while (i > 0 && A[i] > key) {
c5
t
j 2
n
A[i+1] = A[i];
c6
 (t
j
 1)
 (t
j
 1)
j 2
n
i = i -1;
c7
j 2
}
A[i+1] = key;
c8
j
n-1
}
}
tj : while ループが j の値に対して実行される回数
13
INSERTION-SORTの実行時間
T (n)  c1n  c2 (n  1)  c4 (n  1)
n
n
n
j 2
j 2
j 2
 c5  t j  c6  (t j  1)  c7  (t j  1)  c8 (n  1)
tj の値は入力によって変化する.
最良の場合 = 配列が全てソートされている場合
tj = 1
T (n)  c1n  c2 (n  1)  c4 (n  1)  c5 (n  1)  c8 (n  1)
 (c1  c2  c4  c5  c8 )n  (c2  c4  c5  c8 )
 an  b
n の線形関数 (linear function)
14
最悪の場合
• 配列が逆順にソートされている場合
– tj = j
 n(n  1) 
T (n)  c1n  c2 (n  1)  c4 (n  1)  c5 
 1
 2

 n(n  1) 
 n(n  1) 
 c6 
 1  c7 
 1  c8 (n  1)
 2

 2

 an  bn  c
2
n の2次関数 (quadratic function)
15
時間計算量 (Time Complexity)
• アルゴリズムの実行時間は入力に依存する
• アルゴリズムの解析では通常最悪時の実行時
間を考える
– 最悪時の実行時間は任意の入力に対する実行時
間の上界
– 最悪時の実行時間を保証する
– 「最悪時」は頻繁に起きる (データベース検索など)
– 平均時も最悪時と同じくらい悪い (挿入ソートで数
をランダムに挿入)
16
増加のオーダ
• 実行時間の解析を容易にするための抽象化
–
–
–
–
–
各行の実行時間 (コスト) を定数 ci とする
最悪の実行時間を an2+bn+c と表す
実行時間の増加率をみるには主要項 an2 で十分
定数係数も無視
(n2) と表す
• 挿入ソートは (n2) という最悪実行時間を持つ
• あるアルゴリズムが他より効率がよい
⇔最悪実行時間の増加率が低い
17
関数のオーダ
• アルゴリズムの効率を実行時間のオーダで
特徴付け, 相対的な比較を行う
• 入力サイズ n が大きいときの挙動を知りたい
• アルゴリズムの漸近的 (asymptotic) な効率を
調べる
18
漸近記号
-記法
• ある関数 g(n) に対し, (g(n)) は次のような集
合と定義する
(g(n)) = {f(n): 全ての n  n0に対して
0c1 g(n)  f(n)  c2 g(n) となるような
正の定数c1 , c2 , n0 が存在}
( g (n))  { f (n) : c1  0c2  0n0  0n  n0
0  c1 g (n)  f (n)  c2 g (n)}
• f(n) = (g(n)) は f(n)  (g(n)) を意味する
• 2n2+3n+1 = 2n2 + (n) という表現も用いる
19
1 2
n  3n  (n 2 )を示す
2
1 2
全ての n  n0に対して c1n  n  3n  c2 n 2となればいい
2
1 2
2
2
n で割ると c1n  n  3n  c2 n 2
2
1
c2  なら n  1に対して右辺の不等号が成立
2
1
c1  なら n  7に対して左辺の不等号が成立
14
1
1
よって c1  , c2  , n0  7とすれば成立
14
2
2
20
6n  (n )を背理法で示す
3
2
全ての n  n0に対して 6n 3  c2 n 2であるような
定数c2 , n0が存在したとする
任意の大きな nに対して 6n  c2となり矛盾
f (n)  an 2  bn  c  (n 2 )
d
任意の d次多項式p(n)   ai n iに対し (ad  0)
i 0
p ( n )  ( n d )
21
O-記法
• ある関数 g(n) に対し, O(g(n)) は次のような集
合と定義する
O(g(n)) = {f(n): 全ての n  n0に対して
0  f(n)  c g(n) となるような
正の定数c, n0 が存在}
O( g (n))  { f (n) : c  0n0  0n  n0
0  f (n)  cg (n)}
• f(n) = (g(n)) ならば f(n) = O(g(n))
• n = O(n2) も正しい表現
22
• 挿入ソートの実行時間はO(n2)…正解
• 挿入ソートの実行時間は(n2)…間違い
– ソートされた入力に対しては(n)
• 実行時間がO(n2)であるという場合, 最悪実行
時間について言っている
– 実行時間は入力データに依存するため
– 最悪実行時間はデータ数 n のみに依存
23
-記法
• ある関数 g(n) に対し, (g(n)) は次のような
集合と定義する
 (g(n)) = {f(n): 全ての n  n0に対して
0  c g(n)  f(n) となるような
正の定数c, n0 が存在}
O( g (n))  { f (n) : c  0n0  0n  n0
0  cg (n)  f (n)}
• f (n), g(n) に対して f(n) = (g(n)) であるため
の必要十分条件は
f(n) = O(g(n)) かつ f(n) = (g(n))
24
• -記法は下界を表す
• 挿入ソートの最良の実行時間は(n)とは
– このアルゴリズムではどのような入力に対して
も n に比例した時間が必ず必要という意味
• アルゴリズムの実行時間が(n2)とは
– どのような入力に対しても少なくとも n2 に比例
する時間がかかるという意味
25
o-記法 (リトルオー)
• ある関数 g(n) に対し, o(g(n)) は次のような集
合と定義する
o(g(n)) = {f(n): 任意の定数 c > 0 に対し
ある定数 n0 が存在し,
全ての n  n0に対して
0  f(n)  c g(n)}
o( g (n))  { f (n) : c  0n0  0n  n0
0  f (n)  cg (n)}
f ( n)
lim
 0が成り立つ
n  g ( n)
26
• -記法
(g(n)) = {f(n): 任意の定数 c > 0 に対し
ある定数 n0 が存在し,
全ての n  n0に対して
0  c g(n)  f(n)}
• n2/2 = (n)
• n2/2  (n2)
f (n)   ( g (n))  g (n)  o( f (n))
f ( n)
lim
 が成り立つ
n  g ( n)
27
アルゴリズムの設計
• 挿入ソート: 逐次添加法 (incremental approach)
• 分割統治法 (divide-and-conquer) に基づく方法
→マージソート
– 実行時間の解析が容易であることが多い
28
分割統治法
•
問題の再帰的な (recursive) 構造を利用
分割：問題をいくつかの小さな部分問題に分割
統治：各部分問題を再帰的に解く
統合：それらの解を組合わせて元の問題の解を構成
– マージソートでは
分割： n 要素の列を n/2 要素の2つの部分列に分割
統治：マージソートを用いて2つの部分列をソート
統合：2つのソートされた部分列を統合して答を得る
29
マージソート
void MERGE_SORT(data *A, int p, int r, data *B)
{
int q;
// A[p..r] をソート
if (p < r) {
// p==r ならソートする必要なし
q = (p+r)/2;
MERGE_SORT(A, p, q, B); // A[p..q] を再帰的にソート
MERGE_SORT(A, q+1, r, B); // A[q+1..r] を再帰的にソート
MERGE(A, p, q, r, B); // ソートされた部分列 A[p..q] と A[q+1..r] を統合
}
}
30
1
2
2
3
4
5
6
6
2
3
マージ
2
4
5
6
1
マージ
マージ
2
5
4
マージ
5
6
1
4
3
2
マージ
マージ
2
6
6
1
6
マージ
3
2
6
31
マージ
• 一時的な配列 B[0,n-1] を用いる
void MERGE(data *A, int p, int q, int r, data *B)
{
// ソートされた部分列 A[p..q] と A[q+1..r] を統合
int i,j,k;
data t;
k = p; i = p; j = q+1;
while (k <= r) {
if (j > r) t = A[i++];
// 前半のみにデータがある
else if (i > q) t = A[j++];
// 後半のみにデータがある
else if (A[i] <= A[j]) t = A[i++]; // 前半のほうが小さい
else t = A[j++];
// 後半のほうが小さい
B[k++] = t;
// 一時的な配列に保存
}
for (i=p; i<=r; i++) A[i] = B[i]; // 元の配列に書き戻す
}
32
void MERGE_SORT(data *A, int p, int r, data *B) // A[p..r] をソート
{
int q;
if (p < r) {
// p==r ならソートする必要なし
q = (p+r)/2;
MERGE_SORT(A, p, q, B); // A[p..q] を再帰的にソート
MERGE_SORT(A, q+1, r, B); // A[q+1..r] を再帰的にソート
MERGE(A, p, q, r, B); // ソートされた部分列 A[p..q] と A[q+1..r] を統合
}
}
int main(int argc, char *argv[])
{
data A[14] = {27,17,3,16,13,10,1,5,7,12,4,8,9,0};
data B[14];
int i,n;
n = 14;
MERGE_SORT(A,0,n-1,B);
for (i=0;i<n;i++) printf("%d ",A[i]);
printf("\n");
}
33
分割統治アルゴリズムの解析
• 全体の実行時間は問題のサイズに関する漸化式
(recurrence) で記述できることが多い
• サイズ n の問題に関する実行時間を T(n) とする
• n  c (ある定数) ならば定数時間((1))
• 問題を a 個の部分問題に分割し, それぞれが元の
サイズの 1/b 倍になったとすると
(1)
n  cのとき

T ( n)  
aT (n / b)  D(n)  C (n) それ以外
D(n), C(n): 問題の分割, 統合にかかる時間
34
マージソートの解析
• n は2のべき乗と仮定する
• n = 1のとき T(n) = (1)
• n > 1のとき
– 分割： D(n) = (1)
– 統治：再帰的にサイズn/2の部分問題を解く
2T(n/2)
– 統合：MERGEは C(n) = (n)
(1)
n  1のとき

T ( n)  
2T (n / 2)  (n) n  1のとき
T(n)= (n lg n) となる
35
アルゴリズムの重要性
• コンピュータが速くても, 実行時間のオーダ
が大きいアルゴリズムは役に立たない
• スーパーコンピュータで挿入ソートを実行
– 1秒間に1億命令実行
– 2n2 命令必要
• パーソナルコンピュータでマージソートを実
行
– 1秒間に100万命令実行
– 50 n lg n 命令必要
36
• 100万個の数の配列のソート
• ス－パーコンピュータで挿入ソート
2  (106 ) 2 命令
 20,000秒  5.56時間
8
10 命令 / 秒
• パーソナルコンピュータでマージソート
50 106 lg 106 命令
 1,000秒  16.67分
6
10 命令 / 秒
• オーダの低いアルゴリズムの開発が重要
37
問題の計算量
• アルゴリズムの計算量ではなく，問題の計算量
（計算複雑度）という概念がある
• ある問題の計算量が O(f(n)) とは
– その問題を解くあるアルゴリズム A が存在し，
任意の入力に対する計算時間が O(f(n)) である．
– 例：ソーティングの計算量は O(n log n)
(マージソートはどんな入力でも O(n log n) 時間だから)
38
• ある問題の計算量が Ω(f(n)) とは
– その問題に対するどんなアルゴリズムにも，計算時間
が Ω(f(n)) となる入力が存在する
– 例：比較ソートの計算量は Ω(n log n)
証明は後日行う
• ある問題の計算量が (f(n)) とは
– O(f(n)) かつ Ω(f(n))
– 例：比較ソートの計算量は (n log n)
• 計算量の議論をする場合は，計算モデルを明確に
する必要がある
39
クイックソート
• n 個の数に対して最悪実行時間(n2)のソーティ
ングアルゴリズム
• 平均実行時間は(n log n)
• 記法に隠された定数も小さい
• in-place (一時的な配列が必要ない)
40
クイックソートの記述
• 分割統治法に基づく
• 部分配列 A[p..r] のソーティング
1. 部分問題への分割:
–
–
–
配列 A[p..r] を2つの部分配列 A[p..q] と A[q+1..r] に
再配置する．
A[p..q] のどの要素も A[q+1..r] の要素以下にする．
添字 q はこの分割手続きの中で計算する．
2. 部分問題の解決 (統治):
•
部分配列 A[p..q] と A[q+1..r] を再帰的にソート
3. 部分問題の統合
•
A[p..r] はすでにソートされているので何もしない
41
クイックソートのコード
void QUICKSORT(data *A, int p, int r)
{
int q;
if (p < r) {
q = PARTITION(A,p,r);
QUICKSORT(A,p,q);
QUICKSORT(A,q+1,r);
}
}
main()
{
QUICKSORT(A,0,n-1);
}
42
配列の分割
int PARTITION(data *A, int p, int r) // O(n) 時間
{
int q, i, j;
data x, tmp;
x = A[p];
i = p-1; j = r+1;
while (1) {
do {j = j-1;} while (A[j] > x);
do {i = i+1;} while (A[i] < x);
if (i < j) {
tmp = A[i]; A[i] = A[j]; A[j] = tmp;
} else {
return j;
}
}
}
43
A[p..r]
5 3 2 6 4 1 3 7
i
j
5 3 2 6 4 1 3 7
i
A[i]  x
A[j]  x となる最初の i, j
7 は正しい分割位置にある
j
3 3 2 6 4 1 5 7
i
初期状態：
i と j は配列の範囲外
x = A[p] = 5 によって分割
x: 枢軸 (pivot) と呼ぶ
j
A[i] と A[j] を交換
正しい分割位置になる
44
3 3 2 6 4 1 5 7
i
j
3 3 2 1 4 6 5 7
i
A[i]  x
A[j]  x となる最初の i, j
A[i] と A[j] を交換
j
3 3 2 1 4 6 5 7
j i
i  j となったので
q = j を返す
A[p..q] は x 以下
A[q+1..r] は x 以上
45
PARTITIONの正当性
• PARTITIONの返り値を q とする
• A[p..r] の分割後に満たされるべき条件
– A[p..q] はある pivot x 以下
– A[q+1..r] は x 以上
–pq<r
• q = r となると，QUICKSORTは停止しないため，
どんな A に対しても q < r となることを保障する
必要がある
46
• 初期状態は i < j
• do {j = j-1;} while (A[j] > x);
do {i = i+1;} while (A[i] < x); の終了後
–
–
–
–
p  i, j  r
A[j+1..r] は x 以上
A[p..i-1] は x 以下
A[i]  x  A[j]
• i < j のとき，A[i] と A[j] を交換すると
– A[j..r] は x 以上
– A[p..i] は x 以下
• i  j のとき q = j
47
• PARTITIONの終了時に q = j = r とする
– while (1) のループを実行する毎に j は1以上減る
– 終了時に j = r ならばこのループは1度しか実行されて
いない
– しかし1回目のループでは x = A[p] なので i = p
• PARTITIONは p < r の場合のみ呼ばれるので，
1回目のループでは p = i < j = r
• つまり1回目のループでは終了しない
• よってPARTITION終了時に q = r とはならない．
つまり q < r
48
クイックソートの性能
• クイックソートの実行時間は分割が平均化
されているかどうかに依存
• これはpivotの選択に依存
• 分割が平均化されていれば実行時間は漸
近的にマージソートと同じ ((n log n))
• 最悪時は (n2)
49
最悪の分割
• 最悪の場合は，PARTITIONによって領域が
1 要素と n-1 要素に分けられる場合
• 分割には (n) 時間かかる
• 実行時間に対する漸化式は
– T(n) = T(n1) + (n), T(1) = (1)
• T(n) = (n2)
• 最悪実行時間は挿入ソートと同じ
• 入力が完全にソートされているときに起こる
(挿入ソートなら O(n) 時間)
50
n
n
n 1
1
n 1
n2
1
1
n
n
n2
n 3

3
2
2
1
再帰木
1
 
Total :  n
2
51
最良の分割
• クイックソートが最も速く動作するのは，
PARTITIONによってサイズ n/2 の2つの領域
に分割されるとき.
• T(n) = 2T(n/2) + (n)
• T(n) = (n lg n)
• ちょうど半分に分割される場合が最速
52
n
n
n
2
n
2
n
4
n
4
n
4
n
n
4
n
lg n
n n n n n n n n
8 8 8 8 8 8 8 8
n

n
Total : nlg n
53
平衡分割
• PARTITIONで常に 9 対 1 の比で分割されると
仮定する
• T(n) = T(9n/10) + T(n/10) + (n)
• 再帰木の各レベルのコストは O(n)
• 再帰の深さは log 109 n  lg n 
• 漸近的には中央で分割するのと同じ
• 分割の比が 99 対 1 でも同じ (定数比なら良い)
54
クイックソートの
確率的アルゴリズム
• クイックソートの平均的な場合の実行時間を解析
する場合，入力の頻度を仮定する必要がある．
• 通常は，すべての順列が等確率で現れると仮定
• しかし実際にはこの仮定は必ずしも期待できない
• この仮定が成り立たなくてもうまく動作するクイック
ソートの確率的アルゴリズムを示す
55
確率的 (randomized) アルゴリズム
• 動作が入力だけでなく乱数発生器 (randomnumber generator)に依存するアルゴリズム
• 関数 RANDOM(a,b): a 以上 b 以下の整数を
等確率で返すとする．
• プログラミング言語は擬似乱数発生器
(pseudorandom-number generator) を備える
• 擬似乱数: 統計的にはランダムに見えるが，
決定的に作られる数(の列)
56
乱数発生法
• {0, 1, …, p1} の整数を一様ランダムに生成
– C言語
int x;
x = rand() % p; // 整数乱数を p で割った余り
57
乱数の種の設定
• 現在時刻を乱数の種にする
• C言語
srand((int)clock());
srand((int)time(NULL));
58
確率的アルゴリズム1
• クイックソートを行う前に入力配列の要素をラン
ダムに並び替える
• 実行時間は入力順序に依存しなくなる
• アルゴリズムがうまく動作しないのは，乱数発生
器によって運の悪い順列を作る場合のみ
• 最悪の実行時間は改善されない ((n2))
• 最悪の場合はほとんど起きない
59
確率的アルゴリズム2
• 配列を A[p..r] を分割する前に， A[p] と
A[p..r] からランダムに選んだ要素を交換
• pivotが rp+1 個の要素から等確率で選ば
れることを保障する
• 分割が平均的にはバランスのとれたもの
になることが期待できる
60
int RANDOMIZED_PARTITION(data *A, int p, int r)
{
int i;
data tmp;
i = RANDOM(p,r);
tmp = A[i]; A[i] = A[p]; A[p] = tmp; // 値の交換
return PARTITION(A,p,r);
}
void RANDOMIZED_QUICKSORT(data *A, int p, int r)
{
int q;
if (p < r) {
q = RANDOMIZED_PARTITION(A,p,r);
RANDOMIZED_QUICKSORT(A,p,q);
RANDOMIZED_QUICKSORT(A,q+1,r);
}
}
61
最悪の場合の解析
• T(n): サイズ n の入力に対するQUICKSORT
の最悪実行時間
T (n)  max T (q)  T (n  q)  (n)
1 q n 1
• T(n) = O(n2) を示す
• m < n に対し T(m)  cm2 と仮定
62
T (n)  max T (q)  T (n  q )   (n)
1 q  n 1


 c  max q  (n  q)  (n)
2
2
1 q  n 1


 c  1  (n  1)  (n)
2
2
 cn  2c(n  1)  (n)
2
 cn
2
c は 2c(n1) が (n) の項よりも大きくなるように
十分大きくとる
よって T(n) = O(n2) が示された
63
平均的な場合の解析
• T(n): サイズ n の入力に対するRANDOMIZED
QUICKSORTの平均実行時間
• T(n) に関する漸化式を解く
• 入力データはすべて異なる数とする
64
分割の解析
• RANDOMIZED_PARTITIONでPARTITIONが呼
ばれるとき，A[p] の要素は A[p..r] のランダムな
要素と置き換えられている．
• 観察：PARTITIONによって返される q の値は
A[p..r] の中での x = A[p] のランクのみに依存
• x のランク rank(x) = 集合中の x 以下の要素数
• 要素数 n = rp+1
• rank(x) = i となる確率は 1/n
65
• rank(x) = 1 のとき，PARTITIONでのループは
i = j = p で終了
• このとき q = j = p つまり分割の小さい方のサイ
ズは 1．この事象が起きる確率は 1/n
• rank(x)  2 のとき，x = A[p] より小さい値が少
なくとも1つ存在
• PARTITIONでの最初のループ実行後は
i = p，j > p
• A[i] と A[j] を入れ替えるため，x = A[p] は右の
分割に入る
66
• PARTITIONが停止したとき，左の分割には
rank(x)1 個の要素があり，それらは x より小さい
• rank(x)  2 のとき，左の分割のサイズが i である
確率は 1/n (i = 1,2,...,n-1)
• rank(x) が1の場合と2以上の場合を合わせると，
• 左の分割のサイズ rp+1 が
– 1 になる確率: 2/n
– i になる確率: 1/n (i = 2,3,...,n-1)
67
平均時に対する漸化式
• T(n): n 要素の入力配列をソートするのに必要
な平均時間
• T(1) = (1)
• 長さ n の配列に対してソートする場合
– 配列の分割: (n) 時間
– 統治: 長さ q と nq の部分配列を再帰的にソート
n 1

1
T (n)   T (1)  T (n  1)   (T (q)  T (n  q))   (n)
n
q 1

68
T(1)=(1), T(n1) = O(n2) より

1
1
T (1)  T (n  1)  (1)  O(n 2 )
n
n
 O(n)

よって T(n) は次のように書ける
1 n 1
T (n)   (T (q )  T (n  q ))  (n)
n q 1
2 n 1
  T ( k )  ( n )
n k 1
69
m < n に対し T(m)  am lg m + b (a>0, b>0) と仮定
2 n 1
T ( n )   T ( k )  ( n )
n k 1
2 n 1
  (ak lg k  b)  (n)
n k 1
2a n 1
2b

k lg k  (n  1)  (n)

n k 1
n
n 1
1 2
1 2
k lg k  n lg n  n を用いる

2
8
k 1
a
n が (n)+b 以上になるように a を選ぶと
4
70
2a  1 2
1 2  2b
T ( n) 
 n lg n  n   (n  1)  (n)
n 2
8  n
a
 an lg n  n  2b  (n)
4
a 

 an lg n  b   (n)  b  n 
4 

 an lg n  b
T(n) においても成り立つ
よってクイックソートの平均実行時間は O(n lg n)
71
n 1
1 2
1 2
k lg k  n lg n  n の証明

2
8
k 1
n 1
n / 2 1
n 1
k 1
k 1
k  n / 2 
 k lg k   k lg k   k lg k

n / 2 1

k 1
n 1
n 1
n / 2 1
n
k lg   k lg n  (lg n  1)  k  lg n  k
2 k  n / 2 
k 1
k  n / 2 
n 1
n / 2 1
k 1
k 1
 lg n k 
k
1
1n n
 n(n  1) lg n    1
2
22 2
1 2
1 2
 n lg n  n
2
8
72

Download Report