アルゴリズム — 知星図

概要

アルゴリズムとは、問題を解くための「明確な手順」のことです。料理のレシピにたとえられることが多いのですが、レシピと決定的に違う点がひとつあります。「塩少々」「きつね色になるまで」のような曖昧さが一切許されない、ということです。誰が（あるいはどの機械が）実行しても、必ず同じ手順をたどり、有限のステップで答えにたどり着く — この厳密さを備えた手順だけがアルゴリズムと呼ばれます。コンピュータは気を利かせて行間を読んでくれないため、機械に仕事をさせるにはこのレベルの明確さが必要なのです。

プログラミングをしていれば、意識するかどうかにかかわらず毎日アルゴリズムを書いています。一覧を並べ替える、条件に合うデータを探す、最短経路を求める、重複を取り除く — これらはすべて古くから研究されてきたアルゴリズムの定番問題です。そして重要なのは、同じ問題に対して複数の解き方があり、どれを選ぶかで計算の速さが桁違いに変わるという事実です。プログラムの性能は、マシンの速さよりもまず手順の選び方で決まります。

なぜ生まれたか

「明確な手順で問題を解く」という考え方自体は、コンピュータよりはるかに古いものです。名前の由来は9世紀の数学者アル・フワーリズミーで、筆算による計算手順の体系化にさかのぼります。しかし、この概念が厳密に定義されたのは1930年代、チューリングらが「そもそも機械的に計算できるとはどういうことか」を数学的に突き詰めたときでした。人間なら常識で補える曖昧さを完全に排除し、「状態と規則だけで進む手順」として計算を定式化したことが、のちのコンピュータの理論的な土台になります。

コンピュータが実用化されると、今度は「解けるか」だけでなく「現実的な時間で解けるか」が切実な問題になりました。データが増えるほど、素朴な手順と洗練された手順の差は開いていきます。手順そのものを研究対象とし、正しさと効率を体系的に扱う分野としてアルゴリズムは計算機科学の中心に据えられ、その効率を語る共通言語として計算量とO記法が整備されていきました。

詳細

手順の選び方で桁が変わる — 探索の例

アルゴリズムの威力がもっとも分かりやすいのは探索です。100万件の名簿から1人を探すとき、先頭から順に見ていく「線形探索」では最悪100万回の比較が必要です。しかし名簿が五十音順に並んでいれば、「真ん中を見て、目当てがそれより前か後ろかで半分を捨てる」を繰り返す「二分探索」が使えます。1回の比較で候補が半分になるため、100万件でもたった20回ほどで見つかります。データが10億件に増えても30回です。マシンを100倍速くするより、手順を変えるほうが圧倒的に効くことが分かります。

線形探索と二分探索 — 同じ「探す」でも手順が違えば比較回数は桁違いになる

この差は、実際に2つの手順を並べて走らせてみると一目で腑に落ちます。

⚡ 体験: 線形探索 vs 二分探索レース

要素数ターゲット

線形探索 — 先頭から1件ずつ比較 0 回

二分探索 — 真ん中を見て半分を捨てる比較 0 回

ターゲットいま比較中調査済み範囲外（捨てた半分）

マスをクリック（またはランダムボタン）でターゲットを選び、「レース開始」を押してください。

ここには大事な教訓が隠れています。二分探索が使えるのは「データが並んでいる」からです。つまり速いアルゴリズムはしばしば、データの持ち方 — データ構造への投資と引き換えに成立します。並べ替えておくコスト、ハッシュ化による表を維持するコストを先に払うことで、探索という頻繁な操作を劇的に速くする。この「前処理と本処理のトレードオフ」はアルゴリズム設計の基本的な発想です。

評価軸は「正しさ」と「効率」の2つ

アルゴリズムの良し悪しは2つの軸で測ります。第一に正しさ — どんな入力に対しても仕様どおりの答えを返し、必ず停止すること。速くても間違うアルゴリズムには価値がありません。境界条件（空のデータ、重複、最大値）で壊れないかを詰めるのは、正しさの検証そのものです。第二に効率 — 入力が増えたときに時間とメモリがどう伸びるか。これを表す共通言語が計算量とO記法で、「線形探索は O(n)、二分探索は O(log n)」のように、実装やマシンの違いを超えて手順そのものの性質を比較できます。

もうひとつ、設計の定石も知っておくと見通しが良くなります。問題を半分に割って個別に解く「分割統治」（マージソートや二分探索の背後にある考え方）、部分問題の答えを再利用する「動的計画法」、その場の最善を選び続ける「貪欲法」など、多くのアルゴリズムは少数のパターンの応用として理解できます。個々の手順を暗記するより、こうした発想の型を押さえるほうが応用が利きます。

実務のどこに現れるか

「アルゴリズムを書いた覚えがない」という人でも、実務は選択の連続です。ソートや探索は標準ライブラリを呼ぶだけに見えますが、その裏でどんな手順が動いているかは性能に直結します。データベースのインデックスは、まさに二分探索の思想を木構造に展開したもので、貼るか貼らないかの判断は探索アルゴリズムの選択そのものです。経路検索や依存関係の解決にはグラフのアルゴリズム（幅優先探索、ダイクストラ法など）が、キャッシュの追い出しには LRU のような選択アルゴリズムが顔を出します。

一方で、手順を人間が明示的に書き下せない問題もあります。写真に猫が写っているかの判定に「明確な手順」を書くのは絶望的で、こうした領域では大量の例から判定規則そのものを導く機械学習が使われます。手で書ける問題は古典的なアルゴリズムで、書けない問題は学習で — この線引きを知っておくことも、現代のエンジニアにとってのアルゴリズムの素養と言えます。