アルゴリズムとは — 手順が変われば速さが桁で変わる

アルゴリズムとは、問題を解くためのあいまいさのない手順のこと。同じ問題でも、選んだ手順しだいで手数は桁違いに変わります。「64個の数から1つを探すレース」を入口に、正しさと効率という2つの物差しを、動かしながらつかみます。

1. アルゴリズム＝問題を解く「手順書」

アルゴリズムとは、問題を解くための手順を、誰が（何が）実行しても同じ結果になるように書き下したものです。料理にたとえるなら、材料が入力、レシピがアルゴリズム、完成した料理が出力。ただしコンピュータは気を利かせてくれないので、「いい感じに混ぜる」のようなあいまいな指示は許されません。入力を受け取り、有限のステップで必ず止まり、正しい出力を返す — これがアルゴリズムの条件です。

そして大事なのは、同じ問題に対して解き方は1つではないこと。どの手順を選ぶかで、かかる手数がまるで違ってきます。まずはそれを1本のレースで体感しましょう。

POINT — 良いアルゴリズムの2つの物差し ① 正しさ：どんな入力に対しても正しい答えを返すか。② 効率：答えにたどり着くまでの手数（時間）と使う記憶量（メモリ）はどれだけか。正しさは大前提、そのうえで効率を競う。
一歩先へ — 「アルゴリズム」の語源 9世紀バグダッドで活躍した数学者アル・フワーリズミー（al-Khwārizmī）の名が、ラテン語訳で「アルゴリトミ（Algoritmi）」と写され、やがて「計算の手順」を指す言葉になった。さらに彼の著書の題にある「アル・ジャブル（al-jabr）」は代数（algebra）の語源。約1200年前のひとりの名前が、現代コンピュータ科学の中心語彙を2つも生んでいる。

2. 探索対決 — 前から順に見る vs 半分に絞る

問題：「小さい順に並んだ 64 個の数の中から、目標の値を見つけよ」。手順は2つ用意しました。

下のレースで目標の位置を動かしてみてください。二分探索の青い帯（まだ残っている候補範囲）が半分ずつ狭まっていくのがポイントです。

探索レース — 線形探索 vs 二分探索
上段＝線形探索（オレンジ＝いま見ている場所、暗い色＝確認済み）。下段＝二分探索（青い帯＝残っている候補範囲、オレンジ＝いま比べている真ん中）。ピンクの点線が目標値の高さ。目標を右の方に置くほど線形探索は苦しくなりますが、二分探索はどこにあっても最大7回で見つけます。
注意 — 二分探索は「並んでいる」ことが前提 バラバラの列では、真ん中と比べても目標が「どちらの半分にあるか」が分からないので二分探索は使えない。前提条件（ソート済み）を確かめずに使うと、速いどころか間違った答えを返す。アルゴリズムには必ず「効くための条件」がある。
二分探索の最悪比較回数 ≈ log2 N + 1 1回比べるごとに候補が半分になるから。N=64 なら最大 7 回、線形探索は最悪 64 回

3. 手順の設計で手数が変わる — 「上位3つ」を選ぶ

今度は別の問題：「点数の山から上位3つを選べ」。すぐ思いつくのは (a)「全部を点数順に並べ替えて、上から3つ取る」。でも (b)「上位3つのメモだけ持って端から1回だけ眺め、メモの最小値より大きい数が出たら入れ替える」でも同じ答えが出ます。

2つの手順を同時にステップ実行してみましょう。答えは同じなのに、手数がまるで違うことが見えてきます。

「上位3つを選ぶ」2つの手順 — 全部ソート vs 1回走査
上段 (a)＝選択ソートで全部並べ替え（水色＝確定済み、オレンジ＝いま比較中、ピンク＝暫定の最大値）。下段 (b)＝1回だけ走査（右の箱＝覚えている上位3つ）。(b) は箱の中身と比べるだけなので、(a) がまだ並べ替えている間にとっくに終わります。
POINT — 「解ければよい」の一歩先へ (a) は上位3つのためだけに全体を並べ替えるという余計な仕事をしている。問題が本当に要求していることを見極めて手順を設計すると、手数は劇的に減る。これが「アルゴリズムを考える」ということ。

4. N を増やすと差は「爆発」する

64件では「7回 vs 64回」でした。ではデータが1万件、100万件、10億件になったら？ スライダーで N を増やして、最悪の比較回数がどう変わるかを見てください。

N を増やすと — 最悪比較回数の対決（対数目盛）
赤＝線形探索、緑＝二分探索の最悪比較回数。横軸は対数目盛（1目盛りで10倍）。N を10億まで上げても、緑のバーはほとんど伸びません。

線形探索の手数は N に比例して伸びるのに、二分探索は N が2倍になっても +1 回しか増えません。この「増え方の違い」を系統立てて測る道具が、次のレッスンで学ぶ計算量とO記法です。

5. まとめ