アルゴリズム入門 — Project Hematite

データ構造入門では、データの整理の仕方が操作の速さを決めることを学んだ。しかしデータ構造は受動的だ — 特定の配置でデータを保持して待つだけだ。アルゴリズム（algorithm）はその能動的な対になるものだ：データを操作して問題を解く、精密でステップバイステップな手続きだ。

アルゴリズムはソフトウェアのあらゆる場所にある。リストを検索するとき、レコードの集合をソートするとき、ネットワークパケットをルーティングするとき、ファイルを圧縮するとき — そのたびに誰かが慎重に設計したアルゴリズムに頼っている。アルゴリズムが何であるかを理解し、それについて推論し、どれを選ぶかを判断する能力がこのシリーズで養う中核的なスキルだ。

何がアルゴリズムたる条件を満たすか

すべての手続きがアルゴリズムになるわけではない。「好みに合わせて塩を加える」というレシピはアルゴリズムではない — 「好みに合わせて」が曖昧だからだ。永遠に実行し続けるかもしれないループもアルゴリズムではない — 停止の保証がないからだ。アルゴリズムは 4 つの性質を満たさなければならない：

有限性（Finiteness）：すべての有効な入力について有限ステップで終了する。
明確性（Definiteness）：各ステップが正確に仕様化されている — 次に何をするか曖昧さがない。
入出力（Input and output）：0 個以上の入力を受け取り、1 個以上の出力を生成する。
実効性（Effectiveness）：各ステップは人や機械が指示通りに実行できるほど単純だ。

次の記述を考えよう：「リスト中の最大値を見つけるには、左から右へスキャンし、これまでに見た最大値を追跡し続ける。最後にそれを返す。」4 つの性質を確認する：

有限性：ちょうど $n$ ステップでリストの端に達する。
明確性：「左から右へスキャン」「最大値を追跡」は曖昧でない。
入出力：リストが入力、最大値が出力。
実効性：2 数の比較と変数の更新はどちらも基本操作だ。

この単純な手続きはアルゴリズムだ。まもなく最大値の線形スキャンとしてより精密に表現する。

常に問う 2 つの問い

どんなアルゴリズムに出会っても — 自分で書いたものでも教科書で見つけたものでも — 2 つの問いがすぐに重要になる。

正しいか？

正しいアルゴリズムはすべての有効な入力に対して正しい出力を生成する。当たり前に聞こえるが、正しさは驚くほど間違えやすい。オフバイワンエラー、欠けているエッジケース（リストが空だったら？すべての要素が等しかったら？）、入力に関する誤った仮定は実際のシステムにおけるバグの最も一般的な原因だ。

重要な習慣は「このアルゴリズムはすべての有効な入力を正しく処理するか？」と問い、積極的に境界ケースをテストすることだ。正しさを厳密に証明するにはループ不変条件などの形式的手法を使い、これは後のチェックポイントで導入する。

どれくらい効率的か？

正しさは必要だが十分ではない。1 年後に正しい答えを出すアルゴリズムは役に立たない。効率性（efficiency）とは、入力サイズが大きくなるにつれてアルゴリズムのリソース使用量 — 主に時間とメモリ — がどう増えるかを表す。

鍵となる言葉は増え方だ。特定のマシンでの生の実行時間よりも重要なのは：入力サイズが 2 倍になったとき、仕事量は 2 倍になるか？4 倍か？変わらないか？この拡張性（scaling behavior）こそが、あるアルゴリズムが実際の規模で実用的かどうか、あるいはデータが大きくなった瞬間に崩壊するかどうかを決める。

効率性を表現する形式言語が漸近的記法（asymptotic notation）であり、漸近的記法で導入する。

問題とインスタンス

アルゴリズムは一つの問題（problem）全体を解く。特定の 1 つの入力だけではない。例えば：

問題：数のリストを昇順に並べ替えて返す。
インスタンス：[3, 1, 4, 1, 5, 9, 2, 6] が与えられたとき [1, 1, 2, 3, 4, 5, 6, 9] を返す。

問題のためのアルゴリズムはその任意のインスタンスを正しく処理する。この汎用性がアルゴリズムをプログラムやコンテキストをまたいで再利用可能にする。また正しさは一部の例だけでなくすべての有効な入力について示さなければならないことも意味する。

学ぶアルゴリズムのファミリー

このシリーズで扱うアルゴリズムはいくつかの大きなファミリーに分かれ、それぞれが特有の構造とトレードオフを持つ。

探索とソート

探索（searching）アルゴリズムはコレクション内の値を見つけるか、その不在を確認する。線形探索は要素を 1 つずつ調べ、二分探索は各ステップで探索空間を半分にするためソート済みの順序を活用し、大きな入力に対してはるかに良い性能を発揮する。

ソート（sorting）アルゴリズムはコレクションを順序通りに並べ替える。ソート済みデータは効率的な探索や多くの他の操作を可能にし、ソートはコンピュータサイエンスで最も基礎的な問題の一つだ。シンプルだが遅い（挿入ソート）から効率的で広く使われている（マージソート、クイックソート）まで、様々なアルゴリズムを見ていく。

分割統治

分割統治（divide and conquer）アルゴリズムは大きな問題を同種の小さな部分問題に分割し、それぞれを再帰的に解き、結果を結合する。マージソートが典型例だ：リストを半分に分割し、各半分をソートし、2 つのソート済み半分を 1 つのソート済みリストにマージする。

貪欲アルゴリズム

貪欲（greedy）アルゴリズムは各ステップで局所的に最善の選択をし、過去の決定を見直さずにステップバイステップで解を構築する。貪欲アプローチは高速でシンプルだが、常に大局的に最適な解を生み出すわけではない — 貪欲が正しく機能するのはいつかを知ることが重要な設計スキルだ。

動的計画法

動的計画法（dynamic programming）は問題を重複する部分問題に分解し、各部分問題を一度だけ解いてその結果を格納し、冗長な計算を避ける。再帰的アプローチが同じ部分問題を繰り返し計算する場合に適用でき、指数時間の力任せを多項式時間の解に変える。

グラフアルゴリズム

データはしばしば自然なグラフ構造を持つ — 地図、ネットワーク、依存グラフ、状態機械。グラフアルゴリズムはグラフを走査・探索し、その性質を計算する。経路探索、コンパイラ最適化、ソーシャルネットワーク分析など多くのドメインに登場する。

まとめ

アルゴリズムは入力を出力にマッピングする有限・明確・実効的な手続きだ — すべての手続きがアルゴリズムになるわけではない。
4 つの必須性質：有限性、明確性、入出力、実効性。
どんなアルゴリズムについても問うべき 2 つの基本的な問い：正しいか？（すべての有効な入力に対して機能するか？）とどれくらい効率的か？（リソース使用量は入力サイズとともにどう拡張するか？）。
アルゴリズムは問題 — 一般的な仕様 — を解く。特定のインスタンスだけではない。
主なアルゴリズムファミリー：探索とソート、分割統治、貪欲、動的計画法、グラフアルゴリズム。それぞれがシンプルさ・汎用性・効率性の間で異なるトレードオフを持つ。