PowerPoint プレゼンテーションnakano/Al/Al_note1.pdf分割統治法の3ステップ分割統治法は次の3ステップからなる。(分割) 与えられた大きなサイズの問題を、幾つかの(少し小さな)

アルゴリズムI

中野

Note 1

2020.4.23実施

2020.4.06作成

分割統治法

多くの有用なアルゴリズムは再帰的な構造をもっている。

すなわち、与えられた問題を、

その問題に関連した幾つかの部分問題を解くことによって解く。

このようなアルゴリズムを、分割統治法と呼ぶ。

(問題はサイズが小さいほうが簡単に解けることが多いこと

に注意。)

分割統治法の3ステップ

分割統治法は次の3ステップからなる。

(分割) 与えられた大きなサイズの問題を、幾つかの(少し小さな)部分問題に分割する。

(統治) これらの部分問題のそれぞれを再帰的に解く。

(結合) 求められた部分問題の解から、元の問題の解を求める。

分割が高速にできることと、

部分問題の解から元の問題の解が高速に求められることが必要。

解右解左解

分割統治法（再帰アルゴリズム）

分割統治法は一般に下記のように再帰呼び出しを使って書ける。

function Divide-and-Conquer(x)

if x は十分小さいまたは単純である

then 簡単な方法で解き return

(Divide) x を 2個の部分問題 x1, x2 に分割する

(Conquer)

y1 = Divide-and-Conquer(x1)


(Combine)y1と y2 から xの解yを作る

return y

分割統治法（k個に分割する場合）

function Divide-and-Conquer(x)

if x は十分小さいまたは単純である

then 簡単な方法で解き return

(Divide) x を k個の部分問題 x1, x2,… に分割する

(Conquer)



…

yk= Divide-and-Conquer(x2)

(Combine)y1, y2, …から xの解yを作る

return y

分割統治法の例

マージソート, 線型時間( O(n)時間) で中央値を求めるアルゴリズム, 2分探索などは分割統治法である。

他にも膨大な数のアルゴリズムがある。

(Convex Hull, Voronoi diagram, etc.)

多くのアルゴリズムが分割統治法を用いている。

分割統治法はTop Down的な手法である。

(これに対して、動的計画法は Bottom Up的である。)

計算時間 O記法（オーダー記法）

Insertion-Sort(A)

for j=2 to n

begin

key=A[j]

i=j-1

while i>0 and A[i] > key

begin

A[i+1] = A[i]

i = i-1

end

A[i+1] = key

end

3 6 8 11 19 7

123

7が割り込むところを探す

7より大の数字は順に後にずらす

1番からj-1番までソート済みのときj番までソートずみにする

計算時間 O記法（つづき）

Insertion-Sort(A)

for j=2 to n n-1回繰り返し

begin

key=A[j] 1回

i=j-1 2回

while i>0 and A[i] > key 高々n回繰り返し

begin

A[i+1] = A[i] 2回

i = i-1 2回

end

A[i+1] = key 2 回

end

(n-1) (3+4n+2)=4n2 – n -2≦ 4n2

O(n2)

マージソート

Merge-Sort(A,p,r) %配列A のうち、A[p..r]の部分の要素をソートする

if p < r then %まだA[p..r]に要素が２個以上あれば（ソート中）

begin

(Divide) %2つの部分配列 A[p..q] と A[q+1..r] に分割

q ← ( (p+r)/2 を切捨てた整数値 )

(Conquer)

Merge-Sort(A,p,q) %前半を再帰的にソート

Merge-Sort(A,q+1,r) %後半を題記的にソート

(Combine)

Merge(A,p,q,r) %マージして全体のソートを完了

end2 5 7 10 13 16 20 34….4 8 9 11 26 28 32 ….

マージソートの計算時間

n個の要素からなる配列をソートする時間をT(n)とする。

if n＞1 then T(n) = 2 T(n/2) + O(n) となる。

if n＝1 then T(1) = c となる。 (定数回の演算）

これを解くと T(n)は？

注意十分小さなnに対しては、常に、T(n) = c となるので、

これを略してもよいことにする。

(つまり上の例では T(1)=cは略してもよい。)

T(n) = 2 T(n/2) + O(n) の解き方

T(n) ≦ 2 T(n/2) ＋ c n

≦ 2（……………………）＋ cn カッコの中は？

T(n/2) ≦ 2 T(n/4) + c n/2

T(n) = 2 T(n/2) + O(n) の解き方

T(n) ≦ 2 T(n/2) ＋ cn

≦ 2（2 T(n/4) + c n/2 ）＋ cn カッコの中は？

T(n/2) ≦ 2 T(n/4) + c n/2

T(n) = 2 T(n/2) + O(n) の解き方

T(n) ≦ 2 T(n/2) ＋ cn

≦ 2（2 T(n/4) + c n/2 ）＋ cn カッコの中は？

T(n/2) ≦ 2 T(n/4) + c n/2

≦ 2（2 (.........) + c n/2 ）＋ cn カッコの中は？

T(n/4) ≦ 2 T(n/8) + c n/4

T(n) = 2 T(n/2) + O(n) の解き方

T(n) ≦ 2 T(n/2) ＋ cn <=この式はいろいろなｎで成立！

≦ 2（2 T(n/4) + c n/2 ）＋ cn カッコの中は？

T(n/2) ≦ 2 T(n/4) + c n/2

≦ 2（2 (.........) + c n/2 ）＋ cn カッコの中は？

T(n/4) ≦ 2 T(n/8) + c n/4

≦ 2（2 (2 T(n/8) + c n/4) + c n/2 ）＋ cn

= 23 T(n/23) + 3cn

T(n) = 2 T(n/2) + O(n) の解き方

T(n) ≦ 2 T(n/2) ＋ cn <=この式はいろいろなｎで成立！

≦ 2（2 T(n/4) + c n/2 ）＋ cn≦ 2（2 (2 T(n/8) + c n/4) + c n/2 ）＋ cn

= 23 T(n/23) + 3cn

…(log n回展開）

= 2 log n T(n/2 log n) + cn log n

= n T(1) + cn log n x = 2 log n

log x = log n log 2

log x = log n

x = n

O( n log n)

クイックソート

pivot(軸) 前半に74以下の数字を集める

後半に74より大きな数字を集める

74




54 22 18 72

大なのに前のほうにある

629135

小なのに後のほうにある




54 22 18 72


629135


35 72

交換




54 22 18 72


629135


35 7211 85 895814




54 22 18 72


629135


35 72

交換

11 85 895814

14 85




54 22 18 72 629135

35 7211 85 895814

14 85

31 49

完了

あとは、前半を（再帰的に）ソートする後半を（再帰的に）ソートする

マージソートの計算時間

T(n) = ???? (分割の、しかたは一般にはわからない!)

もし、必ず 1個とそれ以外に分割されるとすると（最悪の場合）T(n) = T(n-1) + T(1) + O(n)T(n) ≦ T(n-1) + c1 + c2n

≦ T(n-2) + c1 + c2(n-1) + c1 + c2n= T(n-2) + 2c1 + c2(n + (n-1))≦ T(n-3) + 3c1 + c2(n + (n-1) + (n-2))….≦ T(1 ) + (n-1)c1 + c2n(n-1)/2 O(n2)時間アルゴリズム

The closest pair(最近接ペア）

The closest pair 素朴なアルゴリズム

全ペアの距離をチェック

ans = ∞for i = 1 to n-1

for j = i+1 to nif ans > d(vi , vj)

ans = d(vi , vj)return(ans)

O(n2)時間

n 103 106 109

log n 10 20 30

アルゴリズムの改良（分割統治法）

左右の問題に分ける

左の問題の解を求める ansl

右の問題の解を求める ansr

小さいほうを出力する

だけではダメ！





小さいほうdを出力する


左右の境付近の点のペアを

チェックする








チェックする








チェックする


左右の問題に分ける境界付近の左の各点につき

チェックすべき

境界付近の右の点は高々6個

よって高々6nペアをチェックすればよい

あらかじめy座標でソートしておけば O(n)時間で計算できます

T(n) ≦ 2 T(n/2) + cn

O( n log n) 時間

理解確認クイズT(1)=cは略。nは2のべき乗としてよい。

(1) T(n) = 2 T(n/2) + O(n) を解け。

(2) T(n) = T(n/2) + O(1) を解け。

(3) T(n) = 2 T(n/2) + O(n2) を解け。

(4) T(n) = 2 T(n/2) + O(n3) を解け。

(5) T(n) = 2 T(n/2) + O(n4) を解け。

(6) T(n) = 2 T(n/2) + O(n log n) を解け。

(7) T(n) ≦ 4 T(n/2) + c' n を解け。

(7) T(n) ≦ 4 T(n/2) + c' n を解け。

(1) T(n) = 2 T(n/2) + O(n) の解き方

T(n) ≦ 2 T(n/2) ＋ cn

≦ 2（2 T(n/22) + c n/2 ）＋ cn

= 22 T(n/22) + 2cn

≦ 22 (2 T(n/23) + c n/22）＋ 2cn

= 23 T(n/23) + 3cn


= 2 log n T(n/2 log n) + cn log n

= n T(1) + cn log n

x = 2 log n

log x = log n log 2

log x = log n

x = nO( n log n)

(2) T(n) = 2 T(n/2) + O(1) の解き方

T(n) ≦ 2 T(n/2) ＋ c

≦ 2（2 T(n/4) + c ）＋ c

= 22 T(n/22) + 3c

≦ 22 (2 T(n/23) + c ）＋ 3c

= 23 T(n/23) + 7c


= 2 log n T(n/2 log n) + c(1+2+4+…+2(log n-1))

≦ n T(1) + cn

x = 2 log n

log x = log n log 2

log x = log n

x = nO( n )

12

48

(3) T(n) = 2 T(n/2) + O(n2) の解き方

T(n) ≦ 2 T(n/2) ＋ cn2

≦ 2（2 T(n/22) + c (n/2)2 ）＋ cn2

= 22 T(n/22) + cn2/2 +cn2

≦ 22 ( 2 T(n/23) + c (n/22)2 )＋ (1/2 + 1)cn2

= 23 T(n/23) + (1/22+1/2+1)cn2


≦ 2 log n T(n/2 log n) + 2cn2

= n T(1) + cn2

x = 2 log n

log x = log n log 2

log x = log n

x = nO( n2)

1/81/4

1/21

(3) T(n) = 2 T(n/2) + O(n3) の解き方

T(n) ≦ 2 T(n/2) ＋ cn3

≦ 2（2 T(n/22) + c (n/2)3 ）＋ cn3

= 22 T(n/22) + cn3/22 +cn3

≦ 22 ( 2 T(n/23) + c (n/22)3 )＋ (1/22 + 1)cn3

= 23 T(n/23) + (1/24+1/22+1)cn3


≦ 2 log n T(n/2 log n) + 2cn3

= n T(1) + cn3

x = 2 log n

log x = log n log 2

log x = log n

x = nO( n3)

1/161/4

1/21

Documents

PowerPoint プレゼンテーションnakano/Al/Al_note1.pdf分割統治法の3ステップ 分割統治法は次の3ステップからなる。(分割) 与えられた大きなサイズの問題を、幾つかの(少し小さな)

PowerPoint プレゼンテーションnakano/Al/Al_note1.pdf分割統治法の3ステップ分割統治法は次の3ステップからなる。(分割) 与えられた大きなサイズの問題を、幾つかの(少し小さな)