利用者:Ninomy/アルゴリズム

アルゴリズム

アルゴリズム（algorithm）とは、与えられた問題を解くための効率的手順を定式化した形で表現したものである。ある問題を解く際には、様々なアルゴリズムを考えることができるが、最適なアルゴリズム、最適でなかったとしてもよりよいアルゴリズムを用いて問題を解くことが望ましい。

では、アルゴリズムが「よい」とはどういうことであろうか。大きく3つの事柄が考えられる。

• 正しい結果が得られること
• そのアルゴリズムに基づいて問題を解く操作が「速く」終了すること
• そのアルゴリズムを用いて問題を解く際に用いる資源がなるべく少なくて済むこと

前者は時間的なコスト、後者はリソースのコストがそれぞれ少ないということである。もちろんこの他の要因もあるが、ここではこの3点に絞って考えることとする。

アルゴリズムの完全性

あるアルゴリズムによって問題を解くとき、そのアルゴリズムが備えるべき条件が2つある。

• アルゴリズムに基づいて計算した結果が正しいこと（健全性）
• どのような入力に対しても有限時間内に正しい結果を出力して停止すること（停止性）

この2つの性質を合わせて完全性という。狭義のアルゴリズムは完全性を備えている。

広義には、完全性が必ずしもないものでもアルゴリズムと呼ぶ場合がある。例えば近似アルゴリズムは、近似計算を行うアルゴリズムで、厳密に正しい値は出力されないが実用上問題がない程度に「だいたい」正しい結果を出力できればそれで「よい」ということになる。また、ほとんどの場合で正しい結果を出力して停止する一方、稀にうまくいかないことがある、確率的アルゴリズムもある。

計算量

アルゴリズムの動作の指標として計算量の概念を導入する。

アルゴリズムに基づいて操作を行う時、操作が終了するまでにかかる時間を時間計算量という。また、その時に使用する記憶領域の量を領域計算量という。今日では領域計算量はほとんど問題にする必要がなく、専ら時間計算量について考えることになる。

アルゴリズムの時間計算量を考えるとき、ある問題を解くために何秒かかるか、といった絶対値を考えることはあまり意味がない。むしろ、入力の数（サイズ）が大きくなったときに、計算時間がどのような割合で増大していくか、と言う点が問題になる。

n個の入力があるアルゴリズムを考える。このアルゴリズムの計算時間がnの関数として求められるとき、この関数をPアルゴリズムの計算量という。ただし、同じアルゴリズムであっても入力によって計算が即時に終了する場合もあれば、いつまでも終わらない場合もある。一番時間のかかる場合を仮定して求めた計算量を最悪計算量あるいは最大計算量という。入力の分布が仮定されていれば、計算量の平均を算出することもでき、これを平均計算量という。通常は最大計算量をなるべく小さくするように工夫する。

ただし、計算量が多項式で与えられるとき、もっとも次数の高い項のみに注目すれば十分なことが多く、オーダー記法を用いて表現する。例えばあるアルゴリズムの計算量が

$f(n)=3n^{2}+5n-1$

で与えられたとき、この計算量は$O(n^{2})$であるという。すなわち、nが十分大きければ、nの2乗に比例して時間計算量が増大することを意味する。

時間計算量が指数関数的に増大する関数であるようなアルゴリズムを指数時間アルゴリズムとよぶ。これらは、入力が十分少なければ適切に動作するが、ある程度多い入力では現実的な時間で終了しないプログラムとなり、実用的ではない。

一方、時間計算量がnの多項式関数で与えられるアルゴリズムを多項式時間アルゴリズムと呼ぶ。これらは十分実用的と言えるアルゴリズムである。

アルゴリズムの表現

あるアルゴリズムを表現する方法として、様々な方法がある。例えば、ここでは「電灯が故障したらどうするか」というときの動作を考えることにする。

まず、手順を一つ一つ言葉で説明する方法がある。

1. 電灯がつかない。
2. 電源が入っていなければ、電源を入れる。
3. 電源が入っていても、電球が切れていれば、電球を交換する。
4. 電球が切れていなければ、電灯本体を買い換える。

あるいは、アルゴリズムの動作を図を用いて表現する方法としてフローチャート（flow chart）がある。

フローチャート

また、計算機のプログラミング言語のように、擬似コードを用いて書くこともできる。

// lamp doesn't work..
if (not plugged in) {
  plug in a lamp;
} else {
  if (light is burned) {
    replace bulb;
  } else {
    buy a new lamp;
  }
}

ここでは、特に計算機を用いて解く問題を前提としてアルゴリズムを考えていく。アルゴリズムを計算機上で実行するとき、計算機への命令セットへ記述しなおす必要がある。このような計算機で実行するための命令手順によって書き下した文書をプログラムといい、C言語やJavaといった言語や、あるいはRuby、Pythonなどのスクリプト言語が存在する。

データ構造

アルゴリズムの実行においては、データの集合を構造化して管理する必要のある場合が多い。データにある構造を与えたものをデータ構造（data structure）という。ここでは、種々のデータ構造を見ていくことにする。

リスト

リスト（list, linked list）は配列（array）に似たデータ構造である。n個のデータ列$a_{0},a_{1},a_{2},\cdots ,a_{n-1}$を格納するとき、もっとも単純な方法はn個の配列を用いることである。

C言語による配列の例

int array[3];    // データ列は整数とする
array[0] = 12;
array[1] = 99;
array[2] = 37;

これを用いれば、インデックスを用いて直接データにアクセスすることができる一方、データの挿入や削除を行う際に他のデータをすべて移動させるための手間がかかる。そこで、i番目のデータにi+1番目のデータを指すポインタを付加したデータ構造を考える。

リスト

このようなデータ構造をリストといい、特に次のデータのみを参照することができて逆方向が参照できないものを片方向リスト（singly-linked list）という。

たとえばC言語でこれを実現するためには、データを保持するための構造体を定義すればよい。

C言語によるリスト構造体の例

typedef struct {
  int data;
  struct list_elem *next;
} element;

リストの一つ一つのデータセットをセルという。リストからの要素の削除はポインタの付け替えをすればよく、リストへの要素の挿入はセルの作成とポインタの付け替えをすればよい。