アルゴリズムの解析：RAMモデルと挿入ソートで学ぶ計算量の基本

「アルゴリズム」という言葉は、一言でいえば「何らかの問題を解決するための、手順や処理のしかたの明確な規則」を指す。たとえば「ある数列の中から目的の数を探し出す」「複数のデータを並び替える（ソートする）」「複雑な数値計算を行う」「パズルを解く手順を機械的に表す」といった事柄はすべてアルゴリズムの一例となる。

アルゴリズムには必ず、

• 入力（処理の対象となるデータ、問題設定）
• 出力（得られる結果）
• 明確かつ有限回のステップによる手順

が存在する。たとえば「レシピ」や「数学の定理の証明における一連のステップ」も、広義にはアルゴリズムに相当するが、コンピュータプログラムの世界では、データを機械的に処理するうえでの方法論として特に取り上げられる。アルゴリズムが複雑になればなるほど、計算時間がどのくらいかかるのか、どれほどのメモリを必要とするのかが問題となる。そこで重要になるのが、次に述べるアルゴリズムの解析である。

 

アルゴリズムの解析とは

 

アルゴリズムの解析(analysis of algorithms)とは、与えられたアルゴリズムが入力を受け取って処理を実行するときに、どれほどの計算資源を要するかを予測し・評価し・比較する行為を指す。
ここでいう「計算資源」とは主に次のようなものを含む。

• 実行時間（CPUが命令をじっこうして　完了するまでに費やす時間）
• メモリ使用量（アルゴリズムが途中で利用する変数領域やデータ構造に必要な容量）
• 通信帯域（ネットワーク越しにデータを送受信する場合は、その通信負荷）
• その他のリソース（消費電力や専用ハードウェアの必要性など、特定の分野で重要となる資源もある）

通常、最も注目されるのは実行時間である。特にコンピュータ上のプログラムとしてアルゴリズムを考えるとき、処理が入力サイズの増加とともにどの程度時間を要するかを把握したい場面が多い。そのため、アルゴリズム解析では「入力サイズ\(n\)に対して、実行時間\(T(n)\)がどのように増えるか」を調べ、漸近的(asymptotic)な振る舞いを示す方法がよく採用される。

たとえばソートアルゴリズムを例にすれば、入力として与えられる配列の要素数を\(n\)とし、要素数\(n\)が増大したときにアルゴリズムの実行時間がどのように増えていくのか――例えば\(nlogn\)程度なのか、\(n^2\)程度なのか、といった違い――を見極めることが解析の要点となる。
このとき、低次項や定数係数は無視して、次数の大きな\(n\)での主な増加要素だけを取り出すことで、アルゴリズムのスケーラビリティ（大規模データに対する動作速度）を直感的につかむことができる。これをオーダー記法と呼ぶ。

より厳密なことを言えば、アルゴリズムを解析するときには「どんなモデル（抽象的計算機）を想定して命令を数えるのか？」というモデル化の作業が必要となる。これを行わないと、乗算1回と加算1回をまったく同じ重みで数えるのか、それとも別の重みを割り当てるのか、といった根本的な疑問が解決しないまま曖昧さを残してしまう。そこで用いられる代表的な計算モデルがRAM (Random Access Machine) モデルである。

 

RAMとは

RAMとは？

RAMモデル(Random Access Machine)とは、アルゴリズムを「理想的な計算機上のプログラム」とみなし、そこで行われる各種操作（命令の実行、メモリアクセスなど）に定数時間の重みづけをするという抽象モデルである。
具体的には、次のような前提を置く。

このような理想化は単純化のためであり、解析の基本的な枠組みとしては非常に有用である。実際のプログラムを考えれば、乗算を繰り返すと若干遅くなるかもしれないが、大きなスケール\(n\)を扱うときには「最も重要なのは何回ループを回すか、何回比較をするか」のほうであり、乗算か加算かといった差は定数倍の問題にすぎない、と見なせるからである。

命令について

RAMモデルにおける基本命令は、主に以下のように分類される。

• 算術演算
  加算、減算、乗算、除算、剰余演算、ビット演算（AND,OR,XOR,シフト）など。これらを一回実行するごとに定数コストを課す。
• データ移動
  配列Aの要素\(A[i]\)をレジスタ（データを保存しておく箱のようなもの）に読み込む、レジスタの内容を\(A[i]\)に書き戻す、レジスタ同士のコピーなど。いずれも一回あたり定数コストで考える。
• 制御構造
  条件分岐(if文)や繰り返し(for,while)、関数の呼び出しと戻り(call/return)など。一回の判定や飛び先の設定も定数時間とみなす。

たとえ実際のCPUでは「除算は加算より大きなクロックサイクルを要する」「命令フェッチ・パイプラインなどで分岐予測ミスが起こるとロスが出る」といった現象があっても、RAMモデルはこうした差異をすべて無視し、「1命令あたり一定の時間」とすることで、アルゴリズムの全体的な繰り返し回数・比較回数を解析の中心に据える。

データ型について

RAMモデルでよく扱われるデータ型としては、以下のものが挙げられる。

• 整数型
  必要とされるビット数だけで表現できると仮定し、演算は定数時間で行われるとする。例えば整数\(n\)を取り扱うとき、\(\left\lfloor\log _2 n\right\rfloor+1\)ビットあればその整数を表現できると仮定する。
• 浮動小数点数
  実数の計算を近似的に行うときに使われる。丸め誤差には注意が必要
• 文字
• ブール型（TRUE/FALSE)
  整数値が0(FALSE）か非零(TRUE)かを判定する
• 配列やリスト構造
  メモリ上に連続またはリンク構造で格納され、要素へのアクセスが定数時間またはポインタ追跡のコストで行われる、など抽象化を加える。RAMモデルでは配列 A[i] の参照を定数時間とみなすことが多い。

このように、RAMモデルの前提の下では「一回の演算やメモリアクセスが一定時間」なので、アルゴリズム全体で何回演算やアクセスが起こるかを合計すれば、実行時間の見積もりになるというわけである。

 

挿入ソート

 

ここからは代表的なソートアルゴリズムの一つである挿入ソート（Insertion Sort)を例に、「いかにしてアルゴリズムの実行するか」を具体的に示す。

挿入ソートのアルゴリズム概要

挿入ソートとは、以下のような手順で配列（あるいはリスト）の要素を昇順に並び替えるアルゴリズムである。

1. 配列の先頭部分をすでにソート済みの部分とみなし、そこに未ソート部分から要素を１つずつ取り出して適切な位置に挿入していく。
2. 挿入にあたり、ソート済み部分の末端から順に要素を後ろにずらしながら、挿入すべき場所を探す。
3. すべての要素が挿入されればソート完了。

トランプのカードを手で整列させる場面を想像すると分かりやすい。カードを１枚ずつ手札に加えるとき、そのカードの適切な位置を探して差し込むような動作を繰り返すのが挿入ソートと同じアイデアである。

以下に挿入ソートの典型的な疑似コードを示す。配列\(A\)の要素数を\(n\)とする。ここでは配列のインデックスを１始まりと仮定している。（Pythonなど言語によっては０始まりだが、解析的には問題ない）

 

• １行目では配列の２番目から始めて\(n\)番目要素までを順に「ソート済み部分へと組み込む」処理を繰り返す。
• ２行目で、現在挿入しようとする要素をkeyに保存する
• ４行目で、直前までソート済み部分の末尾を示す添え字jを設定する
• ５～７行目whileループは、keyが挿入されるべき場所を探すために、ソート済みの部分を後方から比較していく。もしA[j]がkeyより大きければ、A[j+1]にA[j]をコピー（シフト）し、jをデクリメントしてさらに前の要素と比較を続ける
• 8行目では、シフトを終えた位置にkeyを挿入する。

簡単な具体例とウォークスルー

例題

A[1…6] = [5, 2, 4, 6, 1, 3]

を昇順（小さい順）にソートする挿入ソートの流れを、部分列を「ソート済み領域」、そこへ「挿入」していくイメージで追っていきます。

初期状態

ステップ 1（i = 2, キー = A[2] = 2）

1. キー　２を取り出す
2. ソート済み領域 [ A[1] ] = [5] と比べると 5 > 2 → 5 を右へシフト。
3. 挿入位置はインデックス１
4. そこへ２を入れる。

ステップ 2（i = 3, キー = A[3] = 4）

1. キー ４を取り出す
2. ソート済み領域[2,5]の右端から：
   ・\(5>4\)→ 5を右へ
   ・次に\(2 \leq 4\)→比較終了
3. ４をインデックス２に挿入。

ステップ 3（i = 4, キー = A[4] = 6）

1. キー　６を取り出す。
2. ソート済み領域[2,4,5]の右端から：
   ・5 ≤ 6 → これ以上シフトせず、そのまま元の位置（インデックス4）へ戻す。

ステップ 4（i = 5, キー = A[5] = 1）

1. キー　１を取り出す
2. ソート済み領域 [2, 4, 5, 6] を右端から順に比べ、すべて > 1 → 6, 5, 4, 2 を順に右へシフト。
3. 挿入位置はインデックス　1
4. 1をそこへ置く。

ステップ 5（i = 6, キー = A[6] = 3）

1. キー　３を取り出す。
2. ソート済み領域 [1, 2, 4, 5, 6] を右端から：
   ・6 > 3 → 6 → 右へ
   ・5 > 3 → 5 → 右へ
   ・4 > 3 → 4 → 右へ
   ・2 ≤ 3 → 比較終了
3. 挿入位置はインデックス３
4. ３をそこへ入れる。

最終結果

全ステップ完了後配列は

[1, 2, 3, 4, 5, 6]

のように昇順に並びます。この例で特に注目すべきなのは、要素１や３を挿入するとき、後ろへのシフトが複数回行われていることである。

こうしたシフトが要素の値や配列の状態によって何回起こるかが、挿入ソートの実行時間を左右する。

 

実行時間の計算

挿入ソ－トの疑似コードをもとに、各行を何回実行するか、そして１回の実行コストはいくらかを数えて合計すると、アルゴリズムの実行時間を得られる。ここでは行ごとに定数コスト\(c_1,c_2,\cdots\)を割り当てる方式をよく用いる。

• 行１：for i = 2 to n
  ループ本体の回数は\(n-1\)回だが、ループを抜けるときも判定を一回行うので、合計\(n\)回判定を行うよって、コストと合わせて実行時間は\(c_1n\)となる。
• 行２：key = A[i] 代入（コピー）１回で定数コスト\(c_2\)。これはforループ内で毎回実行されるので、回数は\(n-1\)回。よって\(c_2(n-1)\)。
• 行４：j = i - 1
  やはりforループの中なので\(n-1\)回。コスト\(c_4\)より合計\(c_4(n-1)\)。
• 行５：while j > 0 and A[j] > key
  ここは要注意。while条件の判定自体は、whileが繰り返されるごとに行われる。
  各回のiにおいて、whileループが何回繰り返されるかを\(t_i\)とおくと、合計判定回数は\(\sum_{i=2}^n t_i\)
  この判定一回あたりのコストを\(c_5\)とすると、合計は\(c_5 \sum_{i=2}^n t_i\)。
• 行６：A[j+1] = A[j] 要素のシフト操作。whileループが実行されるたびに行われる。for文の時と同じく、判定回数より一回減るので\(\sum_{i=2}^n\left(t_i-1\right)\)となる。よって合計は\(c_6 \sum_{i=2}^n\left(t_i-1\right)\)
• 行７：j = j - 1
  同じくwhileループ回数に依存。１回あたりのコストを\(c_7\)とすれば合計\(c_7 \sum_{i=2}^n\left(t_i-1\right)\)
• 行８：A[j+1] = key
  whileを抜けた後、一回だけ実行される。これはforループの各反復で必ず実行されるので、合計\(n-1\)解で\(c_8(n-1)\)。

総合すると、挿入ソートの実行時間\(T(n)\)は次のような形で書ける。

$$
T(n)=c_1 n+c_2(n-1)+c_4(n-1)+c_5 \sum_{i=2}^n t_i+c_6 \sum_{i=2}^n\left(t_i-1\right)+c_7 \sum_{i=2}^n\left(t_i-1\right)+c_8(n-1) .
$$

ここで、\(\sum_{i=2}^n t_i\)は「各\(i\)についてwhileループが何回評価されるか」の合計を表している。具体的な値は配列の並び（要素の初期配置）に大きく左右される。

入力の想定

最悪実行時間

最悪実行時間(worst-case running time)とは、入力サイズ\(n\)のもとで「もっとも時間のかかるような入力」が与えられたときの実行時間をいう。挿入ソートでは、例えば配列が逆順（降順）になっているときが最悪ケースである。

なぜなら、最も小さい要素が配列の末端にあるたびに、挿入の際に最大限シフト（\(i-1\)回程度）を行う必要があるからである。

この場合各ステップで\(t_i =i\)となり、合計すると

$$
\sum_{i=2}^n i=\frac{n(n-1)}{2}
$$

よって、挿入ソートの最悪の場合の実行時間は

$$
\begin{aligned}
T(n)= & c_1 n+c_2(n-1)+c_4(n-1)+c_5\left(\frac{n(n+1)}{2}-1\right) \\
& +c_6\left(\frac{n(n-1)}{2}\right)+c_7\left(\frac{n(n-1)}{2}\right)+c_8(n-1) \\
= & \left(\frac{c_5}{2}+\frac{c_6}{2}+\frac{c_7}{2}\right) n^2+\left(c_1+c_2+c_4+\frac{c_5}{2}-\frac{c_6}{2}-\frac{c_7}{2}+c_8\right) n \\
& -\left(c_2+c_4+c_5+c_8\right)
\end{aligned}
$$

となるが、この場合の実行時間は、再び行のコスト\(c_k\)(ここでは、\(a = c_5/2 + c_6/2 + c_7/2, b= c_1 + c_2 + c_4 + c_5/2 - c_6/2 - c_7/2 + c_8, c = -(c_2 + c_4+ c_5 + c_8) \) )に依存する定数\(a ,b ,c\)を用いて\(a n^2 + bn + c\)を表現できる。したがって、実行時間は\(n\)の二次関数である。

最良実行時間

一方で最良実行時間(best-case running time)とは、入力サイズ\(n\)のもとで「最も速く終わるような入力」が与えられたときの実行時間をいう。挿入ソートでは、すでに昇順で整列済みの配列がそれにあたる。

この場合、要素を挿入しようとするたびwhile ( j > 0 and A[j] > Key)が偽となり( A[j] <= key ですぐ止まる）、シフトが起こらない。つまり各iにたいして\(t_i = 1\)であり最良の実行時間は

$$
\begin{aligned}
T(n) & =c_1 n+c_2(n-1)+c_4(n-1)+c_5(n-1)+c_8(n-1) \\
& =\left(c_1+c_2+c_4+c_5+c_8\right) n-\left(c_2+c_4+c_5+c_8\right)
\end{aligned}
$$

となる。この実行時間は、\(a = c_1 + c_2 + c_4 + c_5 + c_8, b= c_2 + c_4 + c_5 + c_8\)とおいて\(an + b\)と表現できる。

したがって実行時間は\(n\)の線形関数である。

 

最悪か最良か？

一般にアルゴリズムを設計・評価するときには、最悪ケースを重要視することが多い。これは「どんな入力が与えられても、そこからさらにひどい時間はかからない」という上限保証として解釈できるからである。ただし後述する乱択アルゴリズムなどでは、最悪ケースよりも平均ケースや期待値での解析が重視される場合もある。

 

オーダー記法について

多くの場合、最終的にはオーダー記法を用いて、低次項や定数係数を無視した「漸次的な成長度合い」を示す。

オーダー記法には主に三つの種類がある。

\(O\) 記法 (Big-O)	上界を表す 「\(T(n) = O(n^2)\)」とは、ある定数\(k\)と十分大きい\(n_0\)を取れば、\(n > n_0\)で\(T(n) \leq k \cdot n^2\)が成り立つ、という意味 直感的には「\(n\)が大きいとき、\(n^2\)に比例して上から押さえられるということ
\(\Omega\) 記法	下界を表す \(「 T(n)=\Omega(n)\) 」ならば，ある定数 \(k^{\prime}>0\) と \(n_1\) で，\(n>n_1\) のとき \(T(n) \geq k^{\prime} \cdot n\) を満たす。 「少なくとも\(n\)程度で下から押さえられる」という意味
\(\Theta\) 記法	上界と下界の両方が同じ関数形\(f(n)\)で押さえられるとき\(\Theta(f(n))\)で表す。 「\(T(n)=\Theta\left(n^2\right)\) 」は，「 \(T(n)\) は \(n^2\) のオーダーで成長する（2次関数的に押さえ込まれる）」という意味合い。

挿入ソートのオーダー

最良ケース	最悪ケース	平均ケース
\(\Theta(n)\)	\(\Theta(n^2)\)	\(\Theta(n^2)\)

という結論に至る。最良と最悪で大きく差が出るのが特徴である。大量の要素をランダムに並べ替えるような一般的状況では、平均でも\(n^2\)に近い伸びになるため、実用上はやや非効率なアルゴリズムといえる。これに対してもっと高速なソート（マージソート、クイックソート、ヒープソートなど）は、平均や最悪で\(\Theta(n \log n)\)となるため、大きな\(n\)に対してはそちらが好まれる。

 

アルゴリズムの設計：マージソート(Merge-sort)で学ぶ分割統治法の計算量解析

アルゴリズムの設計とは、与えられた問題を解決するための手続き・手順を考案し、それを正しく効率的に実行できるように組み立てる作業のことです。具体的には、入力（問題のデータ）と出力（結果）との間に、どのよ ...

続きを見る