¥¢¥ë¥´¥ê¥º¥à¥¤¥ó¥È¥í¥À¥¯¥·¥ç¥ó ÎØ¹Ö #1

(1)

アルゴリズムイントロダクショ

ン輪講

#1

id:motemen

(2)

よろしくお願いします

(3)

今日やること

1 - 3章イントロダクションアルゴリズムの設計・解析挿入ソートマージソートオーダーの記法関数の増加

(4)

教科書の構成

1 - 5章数学的基礎 6 - 9章ソート 10 章 - 14 章データ構造 1巻ここまで 2 巻以降さらに高度な話題へ

(5)

この本で学べること

アルゴリズムそのもの

アルゴリズムの設計と解析の技法データ構造

(6)

アルゴリズムを学ぶ理由

計算機が無限の速度を持ち、メモリがただで手に入ってもアルゴリズムが停止するか？正しい答えが得られるか？現実に、計算時間・メモリの面で効率の良いアルゴリズムが必要新たな問題に取り組む足掛かりが欲しいなんかかっこいい

(7)

アルゴリズムとは

”ある値または値の集合を入力とし、ある値または値の集合を出力する、明確に定義された計算手続き” → 疑似コード ”明確に定義された計算問題を解くための道具” 問題の例: ソーティング問題入力 n 個の数の列 < a1, a2, . . . , an > 出力 a0₁ ≤ a0₂ ≤ · · · ≤ a0_n であるような入力列の並べ替え < a0₁, a0₂, . . . , a0_n >

(8)

(9)

最初のアルゴリズム

:

挿入ソート

トランプで手札を並べ替えるときに普通やる方法

Google: ”insertion sort” site:youtube.com

ソートされていないカードから 1枚ずつ、ソートされているカードの適切な位置に挿入していく

(10)

挿入ソート

:

疑似コード

procedure Insertion-Sort(A) for j ← 2 to length[A]

do key ← A[j]

i ← j − 1

while i > 0 and A[i] > key do A[i + 1] ← A[i]

i ← i − 1 A[i + 1] ← key 配列は 1 ベース

代入は←

length[A]というのは JS や Ruby の A.length の意 (構造体のメンバへのアクセス)

(11)

アルゴリズムができたらすることは？

アルゴリズムの正当性の検証アルゴリズムは終了するか？アリゴリズムは正しい答えを返すか？アルゴリズムの性能の評価どのくらいの時間がかかるのか

(12)

挿入ソート

:

正当性

アルゴリズムの正当性を検証するために、「ループ不変式」を使用ループ前・中・後で常に成り立つ条件に注目することで、ループの意味を検証する 1回目のループで成り立つ n回目のループで成り立つなら、n + 1 回目でも 成り立つ → ループ終了時に成り立つ

(13)

挿入ソート

:

正当性

アルゴリズムの正当性を検証するために、「ループ不変式」を使用ループ前・中・後で常に成り立つ条件に注目することで、ループの意味を検証する 1回目のループで成り立つ n回目のループで成り立つなら、n + 1 回目でも 成り立つ → ループ終了時に成り立つ

(14)

不変式が満たすべき

3 つの性質

初期条件ループの実行開始直前で成り立つループ内条件ループ中のある繰り返しの直前で成り立つなら、つぎの繰り返しの直前でも成り立つ終了時条件ループが終了したとき、アルゴリズムの正当性の証明を手助けする性質が得られる →不変式: for 文の最初で、部分列 A[1..j − 1] はソートされている

(15)

不変式が満たすべき

3 つの性質

初期条件ループの実行開始直前で成り立つループ内条件ループ中のある繰り返しの直前で成り立つなら、つぎの繰り返しの直前でも成り立つ終了時条件ループが終了したとき、アルゴリズムの正当性の証明を手助けする性質が得られる →不変式: for 文の最初で、部分列 A[1..j − 1] はソートされている

(16)

不変式が満たすべき

3 つの性質

初期条件 A[1..j − 1] は A[1] だけからなる配列なのでソート済みループ内条件ループ中のある繰り返しの直前で成り立つなら、つぎの繰り返しの直前でも成り立つ終了時条件ループが終了したとき、アルゴリズムの正当性の証明を手助けする性質が得られる →不変式: for 文の最初で、部分列 A[1..j − 1] はソートされている

(17)

不変式が満たすべき

3 つの性質

初期条件 A[1..j − 1] は A[1] だけからなる配列なのでソート済みループ内条件 A[j] が正しい場所に挿入されているので OK (while の解析はここではしない) 終了時条件ループが終了したとき、アルゴリズムの正当性の証明を手助けする性質が得られる →不変式: for 文の最初で、部分列 A[1..j − 1] はソートされている

(18)

不変式が満たすべき

3 つの性質

初期条件 A[1..j − 1] は A[1] だけからなる配列なのでソート済みループ内条件 A[j] が正しい場所に挿入されているので OK (while の解析はここではしない) 終了時条件 A[1..j − 1] は A 全体なので配列はソートできた → アルゴリズムは正しい →不変式: for 文の最初で、部分列 A[1..j − 1] はソートされている

(19)

不変式が満たすべき

3 つの性質

初期条件 A[1..j − 1] は A[1] だけからなる配列なのでソート済みループ内条件 A[j] が正しい場所に挿入されているので OK (while の解析はここではしない) 終了時条件 A[1..j − 1] は A 全体なので配列はソートできた → アルゴリズムは正しい →不変式: for 文の最初で、部分列 A[1..j − 1] はソートされている

(20)

アルゴリズムの実行にかかる時間

実行にかかる時間は… 入力に依存始めからソートされていると早い逆順にソートされていると一番遅い → 通常、最悪の場合を考慮 入力のサイズに依存 → 実行にかかる時間を入力のサイズの関数 T (n)で表す

(21)

Insertion-Sort

の実行時間を計算

各ステップの実行回数を計算 (n = length[A]) for j ← 2 to length[A] n

do key ← A[j] n− 1

i ← j − 1 n− 1

while i > 0 and A[i] > key ∑n_j=2tj do A[i + 1] ← A[i] ∑n_j=2(tj − 1) i ← i − 1 ∑n_j=2(tj − 1) A[i + 1]← key n− 1 tj というのは挿入する場所を探す回数 (ループ毎に別々) ループの判定文は本体より 1 回多く実行される

(22)

Insertion-Sort

の実行時間を計算

各行の実行コストに、それぞれの実行回数を掛けたものの和を計算もともとソート済みのとき (最良) while は 1 回しか実行されない: tj = 1 T (n) = an + b の形になる逆順にソートされていたとき (最悪) while が i = 0 になるまで実行される: tj = j T (n) = an2 _{+ bn + c} _{の形になる}

(23)

Insertion-Sort

の実行時間を計算

各行の実行コストに、それぞれの実行回数を掛けたものの和を計算もともとソート済みのとき (最良) while は 1 回しか実行されない: tj = 1 T (n) = an + b の形になる逆順にソートされていたとき (最悪) while が i = 0 になるまで実行される: tj = j T (n) = an2 _{+ bn + c} _{の形になる}

(24)

Insertion-Sort

の実行時間を計算

各行の実行コストに、それぞれの実行回数を掛けたものの和を計算もともとソート済みのとき (最良) while は 1 回しか実行されない: tj = 1 T (n) = an + b の形になる逆順にソートされていたとき (最悪) while が i = 0 になるまで実行される: tj = j T (n) = an2_{+ bn + c} _{の形になる}

(25)

アルゴリズムの実行時間の評価

本当に興味があるのは、実行時間の「増加のオーダー」 (増加率) なので、主要でない項を削ぎ落とす挿入ソートの最悪実行時間は T (n) = an2+ bn + c 挿入ソートの最良実行時間は T (n) = an + b Θ については後で

(26)

アルゴリズムの実行時間の評価

本当に興味があるのは、実行時間の「増加のオーダー」 (増加率) なので、主要でない項を削ぎ落とす挿入ソートの最悪実行時間は T (n) = an2+ bn + c 挿入ソートの最良実行時間は T (n) = an + b Θ については後で

(27)

アルゴリズムの実行時間の評価

本当に興味があるのは、実行時間の「増加のオーダー」 (増加率) なので、主要でない項を削ぎ落とす挿入ソートの最悪実行時間は T (n) = an2+ bn + c = Θ(n2) 挿入ソートの最良実行時間は T (n) = an + b = Θ(n) Θ については後で

(28)

アルゴリズムの実行時間の評価

本当に興味があるのは、実行時間の「増加のオーダー」 (増加率) なので、主要でない項を削ぎ落とす挿入ソートの最悪実行時間は T (n) = an2+ bn + c = Θ(n2) 挿入ソートの最良実行時間は T (n) = an + b = Θ(n) Θ については後で

(29)

(30)

第

2 のアルゴリズム

:

マージソート

マージすべき配列を 2つに分け、それぞれにマージソートをかけた後マージする

Google: ”merge sort” site:youtube.com

分割統治法 (divide-and-conquer)

ちなみに挿入ソートは逐次添加法 (incremental approach)

(31)

分割統治法

問題を部分問題に分解し、その解を組み合わせる

再帰的なアルゴリズムの多くが分割統治法に基づいている

(32)

分割統治の

3 段階

分割問題をいくつかの部分問題に分割する統治部分問題を再帰的に解くただし、部分問題のサイズが十分小さい場合は直接的な方法で解く結合部分問題の解を組み合わせて解を得る

(33)

マージソートでの各段階

分割入力の配列を半分ずつに分割する統治マージソートを用いて部分列を再帰的にソートするただし、入力の長さが 1 であれば何もしない結合ソートされた部分列をマージすることで解を得る

(34)

マージ

2つのソートされた配列をマージして 1つのソートされた配列にする「2つの配列の先頭から小さい方を取る」を繰り返す: Θ(n) その際、配列の最後に ∞ を追加しておくと便利 (番兵)

(35)

マージ

(36)

マージ

(37)

マージ

(

疑似コード

)

procedure Merge(A, p, q, r) n1 ← q − p + 1 n2 ← r − q for i← 1 to n1 do L[i]← A[p + i − 1] for j← 1 to n2 do R[j]← A[q + j] L[n1+ 1]← ∞ R[n2+ 1]← ∞ i← 1 j ← 1 for k← p to r do if L[i]≤ R[j]

then A[k]← L[i]

i← i + 1

else A[k]← R[j]

(38)

手続き

_Merge

の正当性

ループ不変式を以下のようにする A[p..k− 1] には、L と R の要素中で小さい方 から k− p 個がソートされて入っている L[i] と R[j] は、L と R でまだ A に書き戻さ れていない要素のなかでそれぞれ最小

(39)

マージソート

Merge-Sort(A, p, r) 先の Merge 手続きを利用して A[p..r] を ソート p≤ r ならソート済み (0 か 1 要素) なので何も しない分割: dn/2e 要素の A[p..q] と bn/2c 要素の A[q + 1..r]に分割

(40)

マージソート

(41)

マージソート

(42)

マージソート

(

疑似コード

)

配列 A の添字 p から r までをソートする procedure Merge-Sort(A, p, r) if p < r then q ← b(p + r)/2c Merge-Sort(A, p, q) Merge-Sort(A, q + 1, r) Merge(A, p, q, r)

(43)

分割統治アルゴリズムの実行時間

実行時間を T (n) として… 問題のサイズ n が小さいとき定数時間しかかからない (何もしない) T (n) = Θ(1) 問題を a 個の部分問題に分割し、サイズを 1/b にしたとき T (n) = aT (n/b) + D(n) + C(n) D(n): 分割にかかる時間 C(n): 結合にかかる時間

(44)

マージソートの実行時間

分割 bn/2c を計算するだけなので D(n) = Θ(1) 統治問題を 2 個に分割し、サイズが 1/2 になるので a = b = 2, 2T (n/2) 結合 _Merge には Θ(n) 時間かかるので C(n) = Θ(n) なので T (n) = { Θ(1) if n = 1 2T (n/2) + Θ(1) + Θ(n) if n > 1

(45)

マージソートの実行時間

(46)

マージソートの実行時間

T(n)

(47)

マージソートの実行時間

T(n/2) cn

(48)

マージソートの実行時間

T(n/2) cn

T(n/2)

(49)

マージソートの実行時間

cn/2 cn cn/2 T(n/4) T(n/4) T(n/4) T(n/4)

(50)

マージソートの実行時間

cn/2 cn cn/2 T(n/4) T(n/4) T(n/4) T(n/4) T (n/4) = 2T (n/8) + cn/4, . . .

(51)

マージソートの実行時間

cn/2 cn cn/2 T(n/4) T(n/4) T(n/4) T(n/4) c c c c

(52)

マージソートの実行時間

cn/2 cn cn/2 × 2 = cn cn/2 cn/4 cn/4 cn/4 × 4 = cn cn/4 cn/4 c c c × n = cn c c

(53)

マージソートの実行時間

cn/2 cn cn/2 × 2 = cn cn/2 cn/4 cn/4 cn/4 × 4 = cn cn/4 cn/4 c c c × n = cn c c 各段階が cn, 木の深さは log₂n なので T (n) = cn log₂n

(54)

log

₂

n

って

2log2n = n 大雑把に言うと「n を表すのに必要なビット数」 n に対して増え方が遅い log₂256 = 8 log₂65536 = 16 log₂4294967296 = 32 → マージソートは挿入ソートより高速

(55)

log

₂

n

って

(56)

log

₂

n

って

(57)

(58)

関数の増加のオーダーを測る

アルゴリズムの実行時間 T (n) の評価 nが増加したときにどのくらいのスピードで増加するかに興味がある定数部分には興味がない → アルゴリズムの「漸近的」効率を調べる漸近記号 Θ, O, Ω, . . . の導入

(59)

関数の増加のオーダーを測る

(60)

関数の増加のオーダーを測る

(61)

Θ-

記法

f (n) = Θ(g(n)) ⇐⇒ すべての n ≥ n0に対して 0 ≤ c1g(n)≤ f(n) ≤ c2g(n) であるような正の定数 c1, c2および n0が存在する関数の漸近的な増え方を (上下から) 押さえる挿入ソートの実行時間は Θ(n2) ではない 最悪時の実行時間は Θ(n2₎ ここでの = の使い方は濫用なので注意

(62)

O-

記法

f (n) = O(g(n)) ⇐⇒ すべての n ≥ n0に対して 0≤ f(n) ≤ cg(n) であるような正の定数 c および n0が存在する関数の漸近的な増え方を (上から) 押さえる挿入ソートの実行時間は O(n2)

(63)

Ω-

記法

f (n) = Ω(g(n)) ⇐⇒ すべての n ≥ n0に対して 0≤ cg(n) ≤ f(n) であるような正の定数 c および n0が存在する関数の漸近的な増え方を (下から) 押さえる

(64)

o-

記法、

ω-

記法

f (n) = o(g(n)) ⇐⇒ 任意の定数 c > 0 に対してある定数 n0 > 0が存在して、 すべての n ≥ n0に対して 0≤ f(n) ≤ cg(n) である 「漸近的にタイトでない」上界 ω はこの反対

(65)

(66)

関数の増え方

log(x) vs x vs x2 _{vs x}3 _{vs 2}x _0..5 0 20 40 60 80 100 120 140 1 1.5 2 2.5 3 3.5 4 4.5 5 log(x) x x*x x*x*x 2**x

(67)

関数の増え方

log(x) vs x vs x2 _{vs x}3 _{vs 2}x _10..20 0 200000 400000 600000 800000 1e+06 1.2e+06 6 8 10 12 14 16 18 20 log(x) x x*x x*x*x 2**x

(68)

関数の増え方

log(x) vs x vs x2 vs x3 vs 2x 10..20 0 200000 400000 600000 800000 1e+06 1.2e+06 6 8 10 12 14 16 18 20 log(x) x x*x x*x*x 2**x 指数関数ヤバイ

(69)

オーダーに対する簡単な感覚

O(n!) >> O(kn) >> (越えられない壁) >> O(nk_{) > . . .}

O(n3_{) > O(n}2_{) > O(n log n) > O(n) > O(log n) >}

(70)

まとめ

アルゴリズムに入門挿入ソート・マージソートアルゴリズムの正当性アルゴリズムの実行時間オーダー表記

¥¢¥ë¥´¥ê¥º¥à¥¤¥ó¥È¥í¥À¥¯¥·¥ç¥ó ÎØ¹Ö #1

アルゴリズムイントロダクショ

ン 輪講

#1

よろしくお願いします

今日やること

教科書の構成

この本で学べること

アルゴリズムを学ぶ理由

アルゴリズムとは

最初のアルゴリズム

:

挿入ソート

挿入ソート

:

疑似コード

アルゴリズムができたらすることは？

挿入ソート

:

正当性

挿入ソート

:

正当性

不変式が満たすべき

3

つの性質

不変式が満たすべき

3

つの性質

不変式が満たすべき

3

つの性質

不変式が満たすべき

3

つの性質

不変式が満たすべき

3

つの性質

不変式が満たすべき

3

つの性質

アルゴリズムの実行にかかる時間

Insertion-Sort

の実行時間を計算

Insertion-Sort

の実行時間を計算

Insertion-Sort

の実行時間を計算

Insertion-Sort

の実行時間を計算

アルゴリズムの実行時間の評価

アルゴリズムの実行時間の評価

アルゴリズムの実行時間の評価

アルゴリズムの実行時間の評価

第

2

のアルゴリズム

:

マージソート

分割統治法

分割統治の

3

段階

マージソートでの各段階

マージ

マージ

マージ

マージ

(

疑似コード

)

手続き

Merge

の正当性

マージソート

マージソート

マージソート

マージソート

(

疑似コード

ン輪講

_Merge