アルゴリズム

アルゴリズムとは

アルゴリズムとは、ある問題を解くための明確な手順だ。料理のレシピに例えられることが多く、「入力を受け取り、決められた手順を踏んで、目的の出力を得る」ための段取りを指す。同じ問題でも手順は何通りもあり得て、どの手順を選ぶかがプログラムの実行速度やメモリ使用量を大きく左右する。

計算量という指標

アルゴリズムの効率は「計算量」で評価する。データ量が増えたときに、処理時間がどう増えるかを表す指標だ。O 記法は増え方の型だけを示す書き方で、定数倍や影響の小さい項は切り捨てる。そのため同じ O(n) でも実測の速さは実装によって何倍も違い得るし、データ量が小さい範囲では計算量の悪いほうが速いことも珍しくない。

計算量	例	増え方
O(1)	配列の添字アクセス	データ量に依らず一定
O(log n)	整列済み配列への二分探索	データが 1000 倍になっても手数は 10 回ほど増えるだけ
O(n)	全件の線形探索	データ量に比例
O(n log n)	実用的な比較ソート	比例よりわずかに急
O(n²)	二重ループの総当たり	データ量の二乗

データが少ないうちは差が出ないが、大規模になると違いは決定的になる。100 万件から 1 件を探す場合、線形探索は最悪 100 万回の比較が必要なのに対し、二分探索は 20 回ほどで済む。二重ループの総当たりなら比較は 1 兆回規模になり、現実的な応答時間には収まらない。

ただし表の例には前提が付く。二分探索が使えるのはデータが整列済みのときだけで、探すために毎回並べ替えるなら整列そのものに O(n log n) がかかる。1 回しか探さないなら線形探索のほうが速いこともあり、整列された状態を保ち続ける価値が出るのは探索を何度も繰り返す場合だ。もうひとつ気をつけたいのは、示された計算量が最悪の場合を指すのか平均を指すのかという区別で、たとえばハッシュテーブルの検索は平均では O(1) でも、キーが偏れば最悪 O(n) まで落ちる。平均だけを見て設計すると、想定外の入力で急に遅くなる箇所を抱え込むことになる。

なぜ学ぶ価値があるか

主要な言語の標準ライブラリにソートや探索が揃った結果、これらを自分で書き下す機会は減った。それでもアルゴリズムを学ぶ価値は大きい。適切なデータ構造を選ぶ判断、性能問題の原因を見抜く力、計算量で物事を考える習慣は、どの言語・分野でも通用する普遍的な土台になる。

ライブラリを使う側にも、中身の性質を知らないと踏む落とし穴がある。たとえば同じ値のデータどうしの元の並び順が保たれるか (安定性) は、言語や関数によって違う。JavaScript の Array.prototype.sort は ECMAScript 2019 以降の仕様で安定と定められている一方、C++ の std::sort は等しい要素の順序が保たれる保証を持たず、保ちたい場合は std::stable_sort を選ぶ。「点数で並べ替えたら同点者の並び順が崩れた」という不具合は、この違いを知らないまま並べ替えの手段を取り替えたときに起きる。

実務での向き合い方

実務では「最速のアルゴリズムを書く」ことより、「ボトルネックを見極めて適切な手段を選ぶ」ことの方が重要だ。早すぎる最適化は複雑さを生むだけで、多くの場面では素直な実装で十分に動く。一方、大量データを扱う箇所では計算量の知識が効く。どこに効率が必要かを判断する目を養うことが、アルゴリズム学習の実践的な果実になる。

学習には関連書籍が役立つ。