アルゴリズムとデータ構造

アルゴリズムの計算量

実行できる基本演算とそのコストを定めた計算機構を計算モデルという。

ランダムアクセス機械（RAM）

• プログラム：命令の列
• 命令セット
• プログラムカウンタ（PC）
• レジスタ（メモリ単位）：一つの整数もしくは実数を格納

アルゴリズムは計算モデル上で評価する。

RAM を用いたアルゴリズムの評価：実行される命令数がアルゴリズムの計算時間，使用されるレジスタ数がアルゴリズムで使用される記憶領域。

RAM における評価基準：

• 一様コスト基準（uniform cost criterion）：どの命令も単位時間で実行できると仮定
• 対数コスト基準（logarithmic cost criterion）：データを処理する命令では対象のデータの長さ（ビット数）に比例する時間がかかると仮定

アルゴリズムを計算モデルで実行した場合の計算時間（実行した命令数）を時間計算量（time complexity），使用した記憶領域の最大量（使用した最大レジスタ数）を領域計算量（space complexity）と呼ぶ。

入力サイズ（input size） n を変数として計算時間（メモリ量）を表す関数 f(n) を計算量と呼ぶ。

入力サイズ n を大きくしていった時の計算量 f(n) のふるまいを漸進的計算量（asymptotic complexity）という。

十分大きな n に対して f(n) が g(n) の定数倍で上から抑えられるとき，計算量はオーダ（order） g(n) であるといい，O(g(n)) と表記する。

平均計算量（average-case complexity），最悪計算量（worst-case complexity），最良計算量（best-case complexity）

O(n^k) は多項式計算量（polynomial complexity）という。多項式時間計算量を持つアルゴリズムは多項式時間アルゴリズム（polynomial-time algorithm）と呼ばれる。

Ω表記 f(n)=Ω(g(n)) 十分大きな n に対して f(n) が g(n) の定数倍で下から抑えられる

Θ表記 f(n)=O(g(n)) かつ f(n)=Ω(g(n)) のとき，f(n)=Θ(g(n))

グラフ（Graph）

頂点 u と頂点 v を結ぶ辺は e=(u,v) 。u と v は辺 e の端点（end vertex）といい，e は u と v に接続（incident）しているという。u と v は隣接（adjacent）しているという。頂点 u に接続している辺の本数は u の次数（degree）という。e が有向グラフの辺のとき，u は辺 e の始点（initial vertex），v は辺 e の終点（terminal vertex）という。頂点 u を始点とする辺の本数を u の出次数（outdegree）といい，頂点 u を終点とする辺の本数を u の入次数（indegree）という。

DAG：有向閉路を含まない有向グラフ。

連結な無向グラフ G の全ての頂点を含む部分グラフで，木であるものを G のスパニング木（spanning tree）または全域木という。

行列木定理：G のスパニング木の個数は G のラプラシアン L(G) の任意の対角要素に関する余因子の値に等しい。

ラプラシアン L(G) = D − A
D は各頂点の次数からなる対角行列，A は G の隣接行列。

木（Tree）

根から頂点 v への単純路の長さを v の深さ（depth）といい，v から v の子孫への最長の単純路の長さを v の高さ（height）という。

閉路のない無向グラフを森（forest）と呼び，連結な森を木（tree）と呼ぶ。

根を持つ木を根付き木（rooted tree）といい，子の間に順番を考える場合は順序木（ordered tree）と呼ぶ。

各頂点が高々2個の子しか持たない根付き木を 2 分木（binary tree）という。

上から順に頂点が詰まっていて，最下段の頂点は左詰めになっている2 分木を完全 2 分木と呼ぶ。

完全 2 分木は配列で表現可能。 i の親は ⌊(i−1)/2⌋ ，左の子は 2i+1 。

頂点を 1 度ずつ訪れることを走査という。

2 分木における頂点の走査：先行順（preorder）（根→左→右），中間順（inorder）（左→根→右），後行順（postorder）（左→右→根）。

リスト（List, linked list）

セル（cell）＝データ部＋ポインタ部

リストの基本操作：データの挿入・削除・参照・存在判定

リストの利点：挿入・削除が容易，保持できるデータの最大数が可変。

先頭でのみ要素の挿入・削除・参照を行えるリストをスタック（Stack）という。

スタックは後入れ先出し（LIFO）方式のデータ構造。

スタックの基本操作：（先頭に）要素を追加する操作はプッシュ（push），（先頭）要素を取り出す操作はポップ（pop）と呼ばれる。

要素の挿入を一方の端で，削除を他方の端で行うリストをキュー（queue）という。

キューは先入れ先出し（FIFO）方式のデータ構造。

キューの基本操作は挿入・取り出し・参照・削除など。

ヒープ（Heap）

順序集合から最小の要素を繰り返して取り出すためのデータ構造はヒープ（heap），または優先順位付きキューと呼ばれる。

各頂点に順序集合の要素を 1 対 1 に対応させた 2 分木で，親子関係にある頂点間で以下の条件（ヒープ条件）が成立：①親の要素は子の要素より小さい。②根に対応する要素が最小。

ヒープの基本操作：要素の挿入，最小要素（根の要素）の削除，最小要素の参照。

ヒープを常に完全 2 分木とすることで挿入・最小値削除を \(O(\log n)\) で実現可能（頂点数 n の完全 2 分木の高さは \(\lfloor\log n\rfloor\) ）。

完全 2 分木ヒープへの要素の挿入：

1. 完全 2 分木であることを保つ位置に追加したい要素を追加 O(log n)
2. 追加した頂点を注目する頂点に設定
3. 注目している頂点とその親がヒープ条件を満たさなければ，それらの要素を入れ替えて，注目頂点を親に設定し繰り返す
4. ヒープ条件を満たしていれば終了

完全 2 分木ヒープの最小要素の削除：

1. 最も深く最も右にある葉を削除し，その要素を根の要素に書き換える O(log n)
2. 根を注目する頂点に設定
3. 注目している頂点と左右の子がヒープ条件を満たさなければ，ヒープ条件を満たさない子のうちの小さい方と注目頂点の要素を入れ替えて，注目頂点を入れ替えた方の子に設定し繰り返す
4. ヒープ条件を満たしていれば終了

整列 / ソーティング（Sorting）

バブルソート（bubble sort）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void bubblesort(int data[], int n) {
  int i, j, t, sw = 1;
  for (i = 1; sw && i < n; i++) {
    sw = 0;
    for (j = n - 1; j >= i; j--) {
      if (data[j - 1] > data[j]) {
        t = data[j - 1];
        data[j - 1] = data[j];
        data[j] = t;
        sw = 1;
      }
    }
  }
}

挿入ソート（insert sort）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void insertsort(int data[], int n) {
  int i, j, k, t;
  for (i = 1; i < n; i++) {
    for (j = i - 1; j >= 0; j--) {
      if (data[j + 1] < data[j]) {
        t = data[j + 1];
        data[j + 1] = data[j];
        data[j] = t;
      }
      else {
        break;
      }
    }
  }
}

クイックソート（quick sort）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void quicksort(int data[], int first, int last) {
  int i, j, x, t;
  x = data[(first + last) / 2];
  for (i = first, j = last; 1; i++, j--) {
    while (data[i] < x) i++;
    while (x < data[j]) j--;
    if (i >= j) break;
    t = data[i];
    data[i] = data[j];
    data[j] = t;
  }
  if (first < i - 1)
    quicksort(data, first, i - 1);
  if (j + 1 < last)
    quicksort(data, j + 1, last);
}