アルゴリズムイントロダクション第1~2章の個人まとめ

はじめに

今回はアルゴリズムの名著とも言われている以下の本を読み、そのまとめを備忘録の意味合いも兼ねて書き残しておきたいと思います。

<br />

はじめに
第１章「計算におけるアルゴリズムの役割」
第２章「さあ，始めよう」
さいごに

第１章「計算におけるアルゴリズムの役割」

アルゴリズムとは、ある値または値の集合を入力として受け取り、ある値または値の集合を出力として生成する計算手続きである。

データ構造とは、アクセスと更新を容易にする目的のために、データを蓄積し組織化する方法である。

第２章「さあ，始めよう」

ソーティング問題(sorting problem)を取り上げる。

入力：n個の数の列 $< a_1, a_2, ... , a_n >$
出力： $a_1' \leq a_2' , \leq ... \leq a_n'$ である入力列の置換（並べ替え） $a_1', a_2', ... , a_n'$

挿入ソート

まずは挿入ソートについて考える。挿入ソートは少数の要素を効率よくソートするアルゴリズムである。

INSERTION-SORT(A)
1 for j = 2 to A.length
2     key = A[j]
3     // A[j]をソート済みの列A[1 .. j-1]に挿入する
4     i = j - 1
5     while j > 0 かつ A[i] > key
6         A[i+1] = A[i]
7         i = i - 1
7     A[i+1] = key

挿入ソートは $A[1, .. j-1$ ]が以下のループ不変式を定義する。

第1~8行のfor文の各繰り返しが開始されるときには、部分配列A[1 .. j-1]には開始時点A[1 .. j-1]に格納されていた要素がソートされた状態で格納されている

アルゴリズムの正当性を示すためには、ループ不変式を利用し、以下の三つの性質を示す必要がある。

初期条件：ループの実行開始直前ではループ不変式は真である
ループ内条件：ループの何回目かの繰り返しの直前でループ不変式が真ならば、次の繰返しの直前でも真である
終了条件：ループが停止したとき、アルゴリズムの正当性の証明に繋がる有力な性質が不変式から得られる

アルゴリズムの正当性

初期条件：ループ不変式がループの最初の繰り返し（j=2の繰り返し）の直前で成立していることを示す。A[1 .. j-1]はA[1]のみから構成される。よって最初の繰り返しの直前においてループ不変式は真。

ループ内条件：A[j]が入れるべき場所が見つかるまでA[j-1],A[j-2],A[j-3],...を右に移し、空いた場所にA[j]を挿入できているかを検討する。厳密にはwhileループ内のループ不変式を検討する必要があり。

終了条件：ループが停止したときに成立する事実を調べる。停止時はj = n +1である。A[1 .. n]は配列全体であるので、アルゴリズムは正当である。

アルゴリズムの解析

アルゴリズムを解析する上で、ランダムアクセスマシン(RAM)を実現技術として仮定し、アルゴリズムは計算機プログラムとして実現する。

算術演算（加算、減算、乗算、除算、剰余、切り捨て、切り上げ）、データ移動（ロード、ストア、コピー）、制御（条件付きおよび無条件分岐、サブルーチンの呼び出しと復帰）は実行に定数時間しかかからない。

検討する問題に依存して最適な入力サイズの概念は異なる。ソートを含む多くの問題に対する自然な尺度は入力アイテム数、ソートの場合は配列のサイズnである。対して二つの整数の積を計算する問題に対しては、２進表現で入力を表現するのに必要な総ビット数が最適である。アルゴリズムの入力がグラフの場合は入力サイズをグラフの頂点数と変数で記述できる。

特定の入力に対するアルゴリズムの実行時間は、実行される基本演算または「ステップ」の数を指す。

挿入ソートの解析

プログラム	コスト	実行回数
1 for j = 2 to A.length	c1	n
2　　key = A[j]	c2	n-1
3　　// A[j]をソート済みの列A[1 .. j-1]に挿入する	0	n-1
4　　i = j - 1	c4	n-1
5　　while j > 0 かつ A[i] > key	c5	$\sum_{j=2}^{n}t_j$
6　　　　A[i+1] = A[i]	c6	$\sum_{j=2}^{n}(t_j-1)$
7　　　　i = i - 1	c7	$\sum_{j=2}^{n}(t_j-1)$
8　　A[i+1] = key	c8	n-1

アルゴリズムの実行時間は実行された各行の実行時間の合計である。n個の値からなる入力に対する実行時間をT(n)とすると以下で求められる。

$T(n) = c_1n + c_2(n-1) + c_4(n-1) + c_5\sum_{j=2}^nt_j + c_6\sum_{j=2}^n(t_j -1) + c_7\sum_{j=2}^n(t_j -1) + c_8(n-1)$

最良の実行時間( $t_j = 1$ )： $T(n) = (c_1 + c_2 + c_4 + c_5 + c_8)n - (c_2 + c_4 + c_5 + c_8)$

最悪の実行時間( $t_j = j$ )： $T(n) = (\frac{c_5}{2} + \frac{c_6}{2} +\frac{c_7}{2} )n^2 + (c_1+c_2 + c_4 + \frac{c_5}{2} -\frac{c_6}{2}-\frac{c_7}{2} +c_8 )n - (c_2 + c_4 + c_5 + c_8)$

最良時間はnの線形関数にであるが、最悪時間はnの２次関数である。

通常は最悪実行時間だけを考えれば良い。

分割統治法

再帰構造を持つアルゴリズムは多くの場合、分割統治法(divide-and-conquer)に基づいて設計されている。分割統治法は問題を元の問題と類似しているがサイズが小さいいくつかの部分問題に分解し、これらの部分問題を再帰的に解いた後、その解を組み合わせて元の問題に対する解を構築する。

分割；問題をいくつかの同じ問題より小さいインスタンスである部分問題に分割する
統治：部分問題を再帰的に解くことによって統治する。ただし、部分問題のサイズが十分小さい場合は直接的な方法で解く
結合：部分問題の解を組み合わせて元の問題の解を得る。

マージソート

分割：ソートすべき長さnの列を2つの長さn/2の部分列に分割する
統治；マージソートを用いて二つの部分列を再帰的にソートする
結合：二つのソートされた部分列をマージしてソートされた解を得る

分割統治アルゴリズムの解析

アルゴリズムが自分自身を再帰呼び出しをするとき、実行時間を再帰方程式または漸化式で表現できることが多い。

T(n)をサイズnの問題に対する実行時間だとし、ある定数cに対して $n \leq c$ のときには定数時間しかかからないとする。また各問題はa個の部分問題に分割され、各部分問題のサイズは元の問題の1/bとする。問題を部分問題に分割するのにD(n)かかり、部分問題の解を結合して元の問題の解を得るのにC(n)かかるとすると、以下の漸化式を得る。

$T(n) = \begin{cases}\Theta(1) & n \leq cのとき\\aT(\frac{n}{b}) + D(n) + C(n) & それ以外\end{cases}$

マージソートの解析

分割：分割段階では部分列の中央を計算するのみ。 $D(n) = \Theta(1)$ 。
統治：再帰的にサイズn/2の部分問題を二つ得。統治段階には $2T(n/2)$ 時間が必要になる。
結合；n個の要素のマージにかかる実行時間は $\Theta(n)$ なので、 $C(n) = \Theta(n)$ 。