Comment on page
アルゴリズムイントロダクション
- 公式の解答。一部の問題のみ、解答が記載されている
- x 時間
- xxx
- 演習問題は解いていない
- xxx
- アルゴリズムは、ある値または値の集合を入力(input)として取り、ある値または値の集合を出力(output)として生成する、明確に定義された計算手続き
- データ構造は、アクセスと更新を容易にする目的のために、データを蓄積し組織化する方法
- どのデータ構造もすべての目的に対して満足に働くことはない。したがって、いくつかのデータ構造について、その長所と限界を理解することが重要
- 挿入ソート(insertion sort)
- トランプの手札をソートするようなイメージ
- 左手を空にし、テーブルの上にカードを裏向きに置く
- テーブルから 1 枚ずつカードを取って、左手の正しい位置に挿入していく
for j = 2 to A.length
key = A[j]
// A[j]をソート済みの列A[1..j-1]に挿入する
i = j - 1
while i > 0 かつ A[i] > key
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key
- ループ不変式(loop invariant)
- 簡単に言うと、ループの全ての反復に対して、保持される条件
- 厳密に言うと以下の 3 つの性質がある
- 初期条件
- ループの実行開始直前で、ループ不変式は真
- ループ内条件
- ループの何回目かの繰り返しの直前でループ不変式が真ならば、次の繰り返しの直前でも真である
- 終了条件
- ループが停止した時、アルゴリズムの正当性の証明につながる有力な性質が不変式から得られる
- アルゴリズムの解析
- アルゴリズムの実行に必要な資源量を予測することを、アルゴリズムを解析する(analyzing)という
- 多くの場合、測定 したいのは計算時間
- アルゴリズムを解析するには、使用する実現技術のモデルを設定する必要がある。このモデルには実現技術で用いられる資源とそのコストのモデルが含まれる
- 本書では、基本的な単一プロセッサの計算モデルであるランダムアクセスマシン(RAM)を実現技術として仮定し、アルゴリズムは計算機プログラムとして実現する
- RAM モデルでは命令は 1 つずつ逐次的に実行され、並列演算は存在しない
- 実行時間
- ある特定の入力に対するアルゴリズムの実行時間(running time)は、実行される基本演算または「ステップ」の数
- 最悪時と平均時の解析
- 本書では通常の場合、最悪実行時間(worst-case running time)だけを考える
- 以下の 3 つが理由
- 実行時間の上界を知ることで、アルゴリズムの実行にそれ以上の時間がかからないことを保証できる
- あるアルゴリズムでは、最悪の場合がかなり頻繁に生ずることがある
- 平均的な場合が、最悪の場合と同じくらい悪いことが多い
- 増加のオーダ(order of growth)
- 実行時間の増加率が重要
- 例えば挿入ソートだと θ(n^2) となる
- 分割統治法(devide-and-conquer)
- 再帰構造を持つアルゴリズムは、多くの場合、分割統治法に基づいて設計されている
- 分割統治パラダイムの再帰の各レベルは以下の 3 つの段階から構成される
- 分割
- 問題をいくつかの同じ問題のより小さいインスタンスである部分問題に分割する
- 統治
- 部分問題を再帰的に解くことによって統治する。ただし、部分問題のサイズが十分小さい場合は直接的な方法で解く
- 結合
- 部分問題の解を組み合わせて元の問題の解を得る
- マージソート(merge sort)
MERGE-SORT(A, p, r)
if p < r
q = [(p + r) / 2]
MERGE-SORT(A, p, q)
MERGE-SORT(A, q + 1, r)
MERGE(A, p, q, r)
MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
// L[1..n1+1] と R[1..n2+1] を2つの新しい配列とする
for i = 1 to n1
L[i] = A[p + i - 1]
for j = 1 to n2
R[i] = A[q + j]
L[n1 + 1] = ∞
R[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
j = j + 1
- 分割統治アルゴリズムの解析
- 問題を a 個の部分問題に分割され、各部分問題のサイズは元の問題の 1/b であるとする
- また問題を部分問題に分割するのに D(n) 時間かかり、部分問題の解を結合するのに C(n) 時間かかるとする
- 以下の漸化式で表せる
- T = θ(1) (n <= c の時)
- T = aT(n/b) + D(n) + C(n) (それ以外の時)
- このような形式の漸化式を解く方法は 4 章で学ぶ
- マージソートの場合は θ(nlgn)
- θ記法(θ-notation)
- 定義
- ある与えられた関数 g(n) に対して、θ(g(n)) を以下のように定義する
- θ(g(n)) = {f(n): ある正の定数 c1, c2, n0 が存在して、すべての n >= n0 に対して 0 <= c1g(n) <= f(n) <= c2g(n) を満たす}
- 上記の時、g(n) は f(n) の漸近的にタイトな限界(asymptotically tight bound)という
- O記法(O-notation、ビッグオーまたはオー)
- θ記法は関数を漸近的に上下から限定する。漸近的上界(asymptotic upper bound)だけに関心がある時はO記法を用いる
- 定義
- O(g(n)) = {f(n): ある正の定数 c, n0 が存在して、すべての n >= n0 に対して 0 <= f(n) <= cg(n) を満たす}
- Ω記法(Ω-notation、ビッグ オメガまたはオメガ)
- O記法が関数の漸近的上界を与えるのに対し、Ω記法は漸近的下界(asymptotically lower bound)を与える
- 定義
- Ω(g(n)) = {f(n): ある正の定数 c, n0 が存在して、すべての n >= n0 に対して 0 <= cg(n) <= f(n) を満たす}
- o 記法(o-notation、リトルオー)
- 漸近的にタイトでない上界を表すのに o 記法を用いる
- 定義
- o(g(n)) = {f(n): 任意の正の定数 c > 0 に対して、ある正の定数 n0 > 0 が存在して、すべての n >= n0 に対して 0 <= f(n) < cg(n) を満たす}
- ω記法(ω-notation、リトルオメガ)
- 漸近的にタイトでない下界を表すのにω記法を用いる
- 定義
- ω(g(n)) = {f(n): 任意の正の定数 c > 0 に対して、ある正の定数 n0 > 0 が存在して、すべての n >= n0 に対して 0 <= cg(n) < f(n) を満たす}
- 関数の比較
- 推移性
- f(n) = θ(g(n)) かつ g(n) = θ(h(n)) ならば f(n) = θ(h(n))
- f(n) = O(g(n)) かつ g(n) = O(h(n)) ならば f(n) = O(h(n))
- f(n) = Ω(g(n)) かつ g(n) = Ω(h(n)) ならば f(n) = Ω(h(n))
- f(n) = o(g(n)) かつ g(n) = o(h(n)) ならば f(n) = o(h(n))
- f(n) = ω(g(n)) かつ g(n) = ω(h(n)) ならば f(n) = ω(h(n))
- 反射性
- f(n) = θ(f(n))
- f(n) = O(f(n))
- f(n) = Ω(f(n))
- 対称性
- f(n) = θ(g(n)) の時、かつその時に限り g(n) = θ(f(n))
- 転置対称性
- f(n) = O(g(n)) の時、かつその時に限り g(n) = Ω(f(n))
- f(n) = o(g(n)) の時、かつその時に限り g(n) = ω(f(n))
- 漸化式(recurrence)
- 漸化式はある入力に対する関数値を、それより小さい入力に対する関数値を用いて記述する等式または不等式である
- 漸化式を解く方法 3 つ
- 置換え法(substitution method)
- まず限界を推測し、次にその推測が 正しいことを数学的帰納法を用いて証明する
- 再帰木法(recursion-tree method)
- 節点が再帰の各レベルで必要なコストを表現する木の形に漸化式を変形し、和を上または下から抑える技法を用いて漸化式を解く
- マスター法(master method)
- 定数 a >= 1、b >= 1 と与えられた関数 f(n) によって
T(n) = a*T(n/b) + f(n)
と表現できる漸化式に対する限界を与える
- 最大部分配列問題
- 配列 A に対して、要素の和を最大化する A の連続する部分配列を発見する問題
- この連続する部分配列を最大部分配列(maximum subarray)と呼ぶ
- 分割統治による解
- 部分配列の中央点 mid を計算し、部分配列 A[low ... mid] と A[mid+1 ... high] を考察する。すると、最大部分配列 A[i ... j] が見つかるのは以下の 3 つのどこかになる
- 完全に部分配列 A[low ... mid] の中にある。従って low <= i <= j <= mid
- 完全に部分配列 A[mid+1 ... high] の中にある。従って mid + 1 <= i <= j <= high
- 中央点をまたいでいる。従って low <= i <= mid < j <= high
FIND-MAXIMUM-SUBARRAY(A, low, high)
if high == low
return (low, high, A[low]) // 基底。要素数1
else mid = (low + high) / 2
(left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
(right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid + 1, high)
(cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
if left-sum >= right-sum and left-sum >= cross-sum
return (left-low, left-high, left-sum)
else if right-sum >= left-sum and right-sum >= cross-sum
return (right-low, right-high, right-sum)
else
return (cross-low, cross-high, cross-sum)
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = -∞
sum = 0
for i = mid downto low
sum = sum + A[i]
if sum > left-sum
left-sum = sum
max-left = i
right-sum = -∞
sum = 0
for j = mid + 1 to high
sum = sum + A[j]
if sum > right-sum
right-sum = sum
max-right = i
return (max-left, max-right, left-sum + right-sum)
- 行列積
- 単純な分割統治
- 以下を利用する
C11 = A11 * B11 + A12 * B21
C12 = A11 * B12 + A12 * B22
C21 = A21 * B11 + A22 * B21
C22 = A21 * B12 + A22 * B22
- n/2 * n/2 型行列の積の計算は T(n/2) 時間かかる
- 加算にはそれぞれ θ(n^2) 時間かかる
- 以上から
T(n) = θ(1)
n = 1 の時T(n) = 8T(n/2) + θ(n^2)
n > 1 の時
SQUARE-MATRIX-MULTIPLY-RECURSIVE
n = A.rows
// C を新しい n * n 型行列とする
if n == 1
c11 = a11 * b11
else
C11 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11, B11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B21)
C12 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11, B12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B22)
C21 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, B11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B21)
C22 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, B12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B22)
return C
- Strassen の方法
- 8 回あった n/2 * n/2 型行列の計算を 7 回で済ませる
- 10 個の n/2 * n/2 型行列 S1, S2,..., S10 を生成し、7 個の行列積 P1, P2,..., P7 を再帰的に計算する
- すると Strassen のアルゴリズムの実行時間 T(n) は以下のようになる
T(n) = θ(1)
n = 1 の時T(n) = 7T(n/2) + θ(n^2)
n > 1 の時
- 置換え法(substitution method)
- 2 段階で漸化式を解く
- 解の形を推定する
- 数学的帰納法を用いて定数を求め、推定した解がうまく働くことを示す
- 解の正しさを簡潔に証明するのに適しているが、うまい解の推定に苦労することがある
- 再帰木法(recursion tree)
- 再帰木では、各節点はある再帰関数呼び出しに対応する部分問題のコストを表す
- 再帰木の各レベルにおいて、そのレベルに属する節点のコストの総 和を取ることでレベルごとのコストを求め、レベルごとのコストの総和を取ることで再帰木全体のコストを求める
- 再帰木はいい推定を得るための最適の道具。そして得た推定の正しさを置換え法によって検証する
- 漸化式を解くためのマスター法
- a >= 1 と b > 1 を定数、f(n) を関数とする。非負整数上の関数 T(n) を漸化式
T(n) = a * T(n/b) + f(n)
によって定義する。すると T(n) は漸近的に次の限界を持つ- ある定数 ε > 0 に対して f(n) = O(n^logb a-ε) ならば、
T(n) = θ(n^logb a)
- f(n) = θ(n^logb a) ならば、
T(n) = θ(n^logb a * lg n)
- ある定数 ε > 0 に対して f(n) = Ω(n^logb a+ε) であり、しかもある定数 c < 1 と十分大きな全ての n に対して
a * f(n/b) <= c * f(n)
ならば、T(n) = θ(f(n))
- 確率的解析(probabilistic analysis)
- 確率を用いる問題の解析を確率的解析という
- 乱択アルゴリズム(randomized algorithm)
- 一般的に、アルゴリズムの振る舞いが入力と乱数生成器(random-number generator)が生成する値の両方によって決まる時、このアルゴリズムを乱択アルゴリズムと呼ぶ
- 期待実行時間(expected running time)
- 乱択アルゴリズムの実行時間を解析する時には、乱数生成器が返す値の分布の上で実行時間の期待値を取る
- 乱択アルゴリズムの実行時間を期待実行時間と呼ぶ
- PERMUTE-BY-SORTING
- 多くの乱択アルゴリズムでは、与えられた入力配列を置換することで入力をランダム化する。PERMUTE-BY-SORTING はこのやり方の 1 つ。あとでもう 1 つの RANDOMIZE-IN-PLACE を紹介する
- PERMUTE-BY-SORTING は配列の各要素 A[i] に対してランダムに優先度 P[i] を割り当て、A の要素を優先度に従ってソートするやり方
- マージソートに
θ(n * lg n)
時間かかるので、このやり方はΩ(n * lg n)
時間かかる
PERMUTE-BY-SORTING(A)
n = A.length
P[1..n] を新しい配列とする
for i = 1 to n
P[i] = RANDOM(1, n^3) // 1 から n^3 の間で乱数を選ぶ
P をキーとして A をソートする
- RANDOMIZE-IN-PLACE
- これは
O(n)
時間で実現でき、PERMUTE-BY-SORTING より速い
RANDOMIZE-IN-PLACE(A)
n = A.length
for i = 1 to n
A[i] と A[RANDOM(i, n)] を置き換える
- ヒープ(heap)
- (2 分木)ヒープデータ構造は、おおよそ完全 2 分木と見なすことができる配列オブジェクト
- ヒープを表現する配列は 2 つの属性を持つ
A.length
は通常通り配列の要素数を表すA.heap-size
は配列 A に格納されているヒープの要素数を表す
- max ヒープと min ヒープ
- max ヒープ
- 根以外の任意の節点 i が
A[Parent(i)] >= A[i]
の max ヒープ条件を満たすもの
- min ヒープ
- 根以外の任意の節点 i が
A[Parent(i)] <= A[i]
の max ヒープ条件を満たすもの
- 高さ
- ヒープを木とみなした時、ヒープにおける節点の高さを、その節点からある葉に下る最長の単純パスに含まれる変数と定義する
- ヒープの高さは、その根の高さと定義する
- n 個の要素を含むヒープの高さは完全二分木に基づいているので θ(lg n) である
- ヒープ条件の維持
- max ヒープ条件を維持するために手続き MAX-HEAPIFY を呼び出す
- 入れ替える対象となるどちらの子の部分木のサイズも 2n/3 以下だから(最悪の場合、は木の最ものレベルがちょうど半分だけ埋まっている時に起こる)、MAX-HEAPIFY の実行時間は漸化式
T(n) <= T(2n/3) + θ(1)
で表現できる- 計算すると
T(n) = O(lg n)
である
MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap-size かつ A[l] > A[i]
largest = l
else
largest = i
if r <= A.heap-size かつ A[r] > A[largest]
largest = r
if largest != i
A[i] を A[largest] と交換する
MAX-HEAPIFY(A, largest)
- ヒープの構築
- ボトムアップ的に手続き MAX-HEAPIFY を適用することで、配列 A[1..n] を max ヒープに変換できる
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = A.length/2 downto 1
MAX-HEAPIFY(A, i)
- ヒープソートアルゴリズム
- 最初に max ヒープを構築し、そこから順々に最大要素を取り出していく
- 実行時間は
O(n * lg n)
- 実行時間 O(lg n) の MAX-HEAPIFY が n - 1 回呼ばれる
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
A[1] を A[i] と交換する
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
- クイックソート(quick sort)
- 分割統治法の 3 つの段階を以下に示す
- 分割
- 配列 A[p..r] を 2 つの(空の可能性もある)部分配列 A[p..q-1] と A[q+1..r] に、A[p..q-1] のどの要素も A[q] 以下となり、A[q+1..r] のどの要素も A[q] 以上となるように分割(再配置) する。添字 q はこの分割手続きの中で計算する
- 統治
- 2 つの部分配列 A[p..q-1] と A[q+1..r] をクイックソートを再帰的に呼び出すことでソートする
- 結合
- 2 つの部分配列はソート済みだから、これらを結合するために必要な仕事はない。配列全体 A[p..r] はソートされている
QUICKSORT(A, p, r)
if p < r
q = PARTITION(A, p, r)
QUICKSORT(A, p, q - 1)
QUICKSORT(A, q + 1, r)
PARTITION(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
if A[j] <= x
i = i + 1
A[i] を A[j] と交換する
A[i + 1] を A[r] と交換する
return i + 1