アルゴリズム
Algorithm ・ アルゴリズム
問題を解くための明確な手順。同じ問題でも手順の選び方で計算の速さが桁違いに変わる。
✦ 30秒で試す — 航海同じ答えを出す手順でも、速さは何万倍も違うデータを1000倍の10億件に増やすと、最悪の回数は？予想してみる概要
アルゴリズムとは、問題を解くための「明確な手順」のことです。料理のレシピにたとえられることが多いのですが、レシピと決定的に違う点がひとつあります。「塩少々」「きつね色になるまで」のような曖昧さが一切許されない、ということです。誰が（あるいはどの機械が）実行しても同じ手順をたどり、有限のステップで答えにたどり着く — この厳密さを備えた手順だけがアルゴリズムと呼ばれます。コンピュータは気を利かせて行間を読んでくれないため、機械に仕事をさせるにはこのレベルの明確さが必要なのです。
プログラミングをしていれば、意識するかどうかにかかわらず毎日アルゴリズムを書いています。一覧を並べ替える、条件に合うデータを探す、最短経路を求める、重複を取り除く — これらはすべて古くから研究されてきた定番の問題です。そして重要なのは、同じ問題に複数の解き方があり、どれを選ぶかで計算の速さが桁違いに変わることです。その差は、データをどう並べて持つか（データ構造）の選択と一体になって現れます。プログラムの性能は、マシンの速さよりもまず手順の選び方で決まります。
なぜ生まれたか
「明確な手順で問題を解く」という考え方自体は、コンピュータよりはるかに古いものです。名前の由来は9世紀の数学者アル・フワーリズミーで、インド式の筆算の手順を体系化した彼の著作がラテン語に訳され、その名が「計算手順」を指す言葉になりました。紀元前のユークリッドの互除法（2つの数の最大公約数を、割り算の余りを繰り返し取って求める手順）も、現在まで使われている最古級のアルゴリズムです。
しかし「手順」という言葉が数学的に厳密に定義されたのは1930年代です。チューリングやチャーチらが「そもそも機械的に計算できるとはどういうことか」を突き詰め、人間なら常識で補える曖昧さを完全に排除した「状態と規則だけで進む手順」として計算を定式化しました。これがのちのコンピュータの理論的な土台になり、同時に「どんな手順でも解けない問題がある」ことも明らかにしました。
コンピュータが実用化されると、今度は「解けるか」だけでなく「現実的な時間で解けるか」が切実な問題になりました。データが増えるほど、素朴な手順と洗練された手順の差は開いていきます。手順そのものを研究対象とし、正しさと効率を体系的に扱う分野としてアルゴリズムは計算機科学の中心に据えられ、その効率を語る共通言語として計算量とO記法が整備されていきました。
詳細
手順の選び方で桁が変わる — 探索の例
アルゴリズムの威力がもっとも分かりやすいのは探索です。100万件の名簿から1人を探すとき、先頭から順に見ていく「線形探索」では最悪100万回の比較が必要です。しかし名簿が五十音順に並んでいれば、「真ん中を見て、目当てがそれより前か後ろかで半分を捨てる」を繰り返す「二分探索」が使えます。1回の比較で候補が半分になるため、100万件でも20回ほど、10億件でも30回で見つかります（2を30回掛けると約10億）。マシンを100倍速くするより、手順を変えるほうが圧倒的に効くことが分かります。
「10億件でも30回」は、数字で聞くより自分の手で半分を捨ててみるほうが実感できます。下の帯は、小さい順に並んだ10億件のデータです。調べたい場所を押すとその値と目標を比べ、目標がいるはずのない側が捨てられます。どこを押すと一番たくさん捨てられるかを試してみてください。
帯は小さい順に並んだ 10億件のデータです。帯の中を押すと、その番地の値を目標と比べます。まずは真ん中あたりを押してみてください。
真ん中以外を押すと、運が良ければ大きく捨てられますが、運が悪いとほとんど捨てられません。真ん中は「どちらに転んでも半分」を保証する唯一の場所で、それが最悪でも30回という保証になります。
ここには大事な教訓がもう1つ隠れています。二分探索が使えるのは「データが並んでいる」からです。つまり速いアルゴリズムはしばしば、データ構造への投資と引き換えに成立します。並べ替えておくコスト、ハッシュ化による表を維持するコストを先に払うことで、探索という頻繁な操作を劇的に速くする。この「前処理と本処理のトレードオフ」はアルゴリズム設計の基本的な発想です。
正しさ — 必ず答えを返し、必ず止まる
アルゴリズムの良し悪しは「正しさ」と「効率」の2つの軸で測ります。速くても間違う手順には価値がないので、まず正しさです。正しさには2つの面があります。どんな入力に対しても仕様どおりの答えを返すこと（部分正当性）と、必ず有限の手数で止まること（停止性）です。
二分探索で考えてみます。正しさを支えるのは「目標が存在するなら、それは必ず範囲 [lo, hi] の中にある」という性質で、これを「ループ不変条件」と呼びます。最初は全体が範囲なので成り立ち、真ん中と比べて目標がいない側を捨てても成り立ち続けます。一方、停止性を支えるのは「1周ごとに範囲が必ず狭くなる」ことです。範囲の幅は正の整数で、毎回少なくとも1は減るので、いつか必ず尽きます。
この2つを意識すると、二分探索の定番のバグの正体が見えます。mid を捨てずに lo = mid と書くと、範囲が2件になったところで狭まらなくなり、無限ループになります（停止性の破れ）。hi = mid - 1 の境界を1つ間違えると、目標をうっかり捨ててしまいます（不変条件の破れ）。空の配列、要素が1個、目標が先頭・末尾・存在しない、といった境界のテストは、まさにこの2つを確かめる作業です。
設計の型 — 分割統治・動的計画法・貪欲法
多くのアルゴリズムは、少数の発想の型の応用として理解できます。個々の手順を暗記するより、型を押さえるほうが応用が利きます。
分割統治は、問題を同じ形の小さな問題に割り、それぞれを解いてから答えを組み合わせる型です。代表はマージソートで、「半分に割ってそれぞれを並べ替え、並んだ2列を先頭から比べながら1列に合わせる」を、1個になるまで再帰で繰り返します。割る段は log n 段あり、各段で合わせる作業は全体で n 回なので、合計は n log n に比例します。二分探索も「半分に割って片方だけ解く」分割統治の仲間です。
動的計画法は、同じ部分問題が何度も現れるときに、その答えを表に記録して使い回す型です。素朴な再帰でフィボナッチ数を求めると、同じ値を指数的な回数だけ計算し直しますが、小さい順に表を埋めれば n 回で済みます。2つの文字列の差分（diff）や、乗り換え案内の最小運賃のように、「小さな問題の最適解を組み合わせると大きな問題の最適解になる」構造を持つ問題で力を発揮します。
貪欲法は、その場その場で一番良く見える選択を続け、後戻りしない型です。硬貨の枚数を最小にする両替（1・5・10・50・100・500円なら、大きい硬貨から使えば最適）や、地図の最短経路を求めるダイクストラ法がその代表です。速くて単純ですが、どの問題でも最適解に届くわけではありません。1・4・6円の硬貨で8円を払うとき、貪欲に6円から使うと 6+1+1 の3枚ですが、最適は 4+4 の2枚です。貪欲法を使うときは「その場の最善が全体の最善になる」ことを証明しておく必要があります。
効率と実務
もう1つの軸が効率 — 入力が増えたときに時間とメモリがどう伸びるかです。これを表す共通言語が計算量とO記法で、「線形探索は O(n)、二分探索は O(log n)、マージソートは O(n log n)」のように、実装やマシンの違いを超えて手順そのものの性質を比べられます。
「アルゴリズムを書いた覚えがない」という人でも、実務は選択の連続です。ソートや探索は標準ライブラリを呼ぶだけに見えますが、その裏でどんな手順が動いているかは性能に直結します。データベースのインデックスは二分探索の思想を木構造に展開したもので、貼るか貼らないかの判断は探索アルゴリズムの選択そのものです。経路検索や依存関係の解決にはグラフのアルゴリズム（幅優先探索、ダイクストラ法など）が、キャッシュの追い出しには LRU（最も長く使われていないものから捨てる）のような方針が顔を出します。
一方で、手順を人間が明示的に書き下せない問題もあります。写真に猫が写っているかの判定に「明確な手順」を書くのは絶望的で、こうした領域では大量の例から判定規則そのものを導く機械学習が使われます。ただしその学習も、勾配降下法という明確な手順で動いています。手で規則を書ける問題は古典的なアルゴリズムで、書けない問題は「規則を学ぶ手順」で — この線引きを知っておくことも、現代のエンジニアにとってのアルゴリズムの素養です。
試問
小さい順に並んだ100万件のデータの帯です。帯の中を押すと、その番地の値と目標の値を比べ、目標がいるはずのない側が捨てられて、帯は残りの範囲に拡大されます。押す場所は毎回自由に選べます。
帯は小さい順に並んだ 100万件のデータです。帯の中を押すと、その番地の値を目標と比べます。