アルゴリズムと計算量、基本的なデータ構造
目次
1. アルゴリズムとは
アルゴリズムとは与えられた問題を解くための手順のことです。アルゴリズムは明確な手順を記した疑似コードという形とよばれる表現方法で記述されることが多いです。疑似コードから計算機プログラムへの変換の例として、ユークリッドの互除法のアルゴリズムを紹介します。
例1-1:ユークリッドの互除法
疑似コード
Euclid(m, n) { //整数mとnの最大公約数を返す
以下の操作を繰り返す
mをnで割ってあまりをrとする
もしr=0であれば、計算結果としてnを返し終了
mにnを代入して、nにrを代入する
}
これをもう少しプログラムらしくすると下のようになります。
int Euclid(int m, int n) { //整数mとnの最大公約数を返す
repeat
r << mをnで割ったあまり;
if (r = 0) return n;
m << n, n << r;
}
新しい問題を解くためには、自分で新しい問題を解くかなければならないですが、そのためにはまず疑似コードのレベルでプログラムを設計することが大事です。
2. 計算量
アルゴリズムの計算量とは、入力として与えられたデータの大きさに対して、計算の手間がどれくらいになるかを
の関数として、見積もったものです。普通に考えるとプログラムの動作にかかる時間で議論すべきですが、これは実行する計算機の性能に依存してしまうためアルゴリズム本来の効率を議論するのに適しません。計算量という概念をもう少し明確に定義すると、正定数
が存在して、すべての
で、
となるとき、
表記します。
3. 配列とリスト
複数のデータが順序を持って並んだもの（列）は計算機が扱うデータの中で最も基本的なものです。列を表現するためには大きく分けて配列による表現とリストによる表現があります。それぞれ短所と長所があるので、プログラムの目的によって適切に使い分ける必要があります。
配列
配列による表現は、あらかじめ確保された連続した領域に要素をしまうもので、列の何番目かの要素を指定すると。の計算時間で即座にその位置の要素を取り出すことのできるデータ構造です。しかし、列の途中に要素を追加する場合は、それ以降の要素を一つずつ後ろにずらしてあげる必要があり、列の途中の要素を削除する場合はそれ以降の要素を前にずらしてあげる必要があります。どちらも
の計算時間がかかります。
リスト
リストによる表現は、要素一つ一つに独立した領域をもたせ、次の要素を格納している場所を示すポインタを前の要素に持たせておくことで全体を辿れるようにしたものです。配列と違いi番目の要素を取り出すには、前から順に辿って行かなければならず、の計算時間がかかります。しかし、列の途中に要素を追加したり、削除したりするのには、一つ前の要素と挿入したポインタを付け替えるだけで済むので、計算時間は
で済みます。
以上のように、列へのアクセスが多く長さがあまり変わらないときは配列、逆に列の要素の追加や削除が多く、要素にアクセスするときは最初から順番に取り出すことが多い場合は、リストを使うと良いでしょう。
配列とリストの実装
通常の手続き型言語でデフォルトで用意されているのは配列です。リストを使うためには、自分で実装するか、ライブラリを利用するといいでしょう。ライブラリを利用するときは、実際の実装が明らかになってないことも多いので注意してください。
4. スタックとキュー
スタックとキューについては別の記事で説明したことがあるので、説明を割愛させていただきます。リンク先の記事を参照してください。
キューの実装に当たっては、配列を用いて単純に実装すると、dequeするたびに配列を前に詰める操作が必要になってしまいます。これを避けるために一連の配列領域の先頭と最後尾がリング状に繋がっているとみなして、データの先頭番地と最後尾番地を保持する循環行列という方法があります。
5. 木
木は一つの根のしたのに多数のノードが階層構造をもって接続されているデータ構造であり、一つの親ノードの下に複数の子ノードが接続された形となっています。子を持たない末尾のノードは葉と呼ばれます。データのアクセスは通常根を起点として、中間ノードを辿っていくことで実現されます。木の表現方法としてはセルをポインタで繋いだものが一般的ですが、一つの親ノードに接続される子ノードの個数が一定である場合には配列による表現も可能です。
