同じ答えにたどり着く手順が2つあったとき、どちらが良いのでしょうか。正しさが同じなら、次に見るのは手数です。
辞書で「たまご」を引く
紙の辞書で言葉を探す方法を2つ考えます。
- 方法A: 1ページ目から順にめくって探す
- 方法B: まん中を開く。目的の語より後ろなら前半を、前なら後半を捨てる。残った範囲でまた、まん中を開く
1000ページの辞書で比べます。方法Aは、運が悪ければ1000回めくります（平均500回）。方法Bは、1回ごとに範囲が半分になるので、1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1 で約10回です。
100倍近い差です。しかも辞書が10万ページに増えても、方法Bは17回程度しか増えません。データが増えたときの伸び方が違う——ここが効率の話の核心です。
この方法Aを線形探索、方法Bを二分探索と呼びます。第4部でC言語として自分の手で書くことになりますが、大事なのは名前ではなく、半分に割る発想そのものです。
ただし、方法Bには条件がある
二分探索が使えるのは、あらかじめ並んでいる場合だけです。辞書は五十音順に並んでいるから半分に割れます。バラバラの紙の束では使えません。
つまり効率の良い手順には、たいてい前提条件が付きます。「速いほうを選ぶ」ではなく、「その前提が成り立つか」を確かめる。これが正しい順序です。
手数の数え方に慣れる
アルゴリズムを比べるときは、データの個数を n として「n が増えると手数はどう増えるか」を見ます。
- 全部を1回ずつ見る → n 回（データが10倍なら手数も10倍）
- 半分に割り続ける → 約 log2(n) 回（データが10倍でも手数は3〜4回増えるだけ）
- 全部の組み合わせを見る → n × n 回（データが10倍なら手数は100倍）
最後の型はとくに注意が必要です。手元の10件では一瞬でも、本番の1万件では数時間かかる、ということが起こります。この考え方には計算量という名前があり、第4部でO記法として学びます。
身近な例で言えば、写真フォルダから重複を探す処理が最後の型です。「全部の組み合わせを比べる」やり方だと、1万枚では約5000万回の比較になります。1秒に1000万回比べられるとしても5秒。10万枚なら100倍の約8分です。枚数が10倍で時間が100倍という伸び方の怖さが、少し実感できるでしょうか。
とはいえ、最初から凝らない
初心者がやりがちな失敗は、動く前から速さを気にしてコードをこねくり回すことです。順番は決まっています。
- まず正しく動くものを作る
- 遅くて困ったら、どこが遅いかを測る
- 測った場所だけ直す
推測するな、測れというのが、この世界の古い格言です。今の段階では「手順しだいで桁が変わることがある」という予感だけ持っておけば十分です。