もしあなたが、友達の家でバラバラになった1000巻の漫画を片付けようとして、「まず1巻を探して左端に置き、次に2巻を探してその右に置く」という手順を迷わず選んだとしたら。
残念ながら、コンピュータ科学の世界では、あなたはこう一蹴されてしまうでしょう。
「あのね、それダッサいっすね。……え、オミクロンN2乗のアルゴリズムじゃん」
私たちが「丁寧で確実な仕事」だと思い込んでいるその手順は、実はデータの量が増えた瞬間に破綻する、きわめて危うい「ダサい努力」の典型なのです。なぜ、1巻から順番に探してはいけないのか？ なぜ、ITエンジニアは「2乗」という言葉を聞いただけで顔をしかめるのか？
今回は、日常の整理整頓から、仕事の生産性を劇的に変える「 $\log$ の魔法」まで、アルゴリズムの良し悪しを決める決定的な指標「オーダー（計算量）」について、心地よい驚きとともに解説します。
今回の配信内容🎧
- 1000巻の漫画を例に学ぶ、アルゴリズムを評価するたった一つの基準。
- 直感的な「1冊ずつ探す方法」が、なぜデータ量が増えると「地獄」に変わるのか。
- コンピュータ科学の最重要単語「オーダー（ $O$ 記法）」の正体。
- 数学の魔法「 $\log$ 」を使いこなし、1兆回の作業を2000万回にショートカットする知略。
あなたの漫画並び替え方法は「ダサい」？選択ソートという罠
バラバラの漫画を並べる際、多くの人が直感的に選ぶ「1冊ずつ場所を確定させていく方法」は、コンピュータ科学では「選択ソート（セレクションソート）」と呼ばれます。
手順は極めて明快です。
- バラバラの山から「1巻」を探し出し、本棚の左端に置く。
- 残りの山から「2巻」を探し出し、1巻の隣に置く。
- これを最終巻まで繰り返す。
誰でもできる立派なアルゴリズムに見えますが、アルゴリズムの評価軸はたった一つ、「早く終わったほうが偉い」というシビアな世界です。PCのスペックがどれほど進化しても、この評価基準は揺らぎません。そこで重要になるのが「計算の回数（比較した回数）」です。
例えば1000巻の漫画を並べるとき、最初の1巻を探すためには、最悪の場合1000冊全てをチェックしなければなりません。次に2巻を探すときは999冊、3巻なら998冊……。平均すると、毎回「残りの冊数の半分」を確認していることになります。
この「平均500回のチェック」を1000回繰り返すと、合計の計算回数は約50万回。
「2乗に関する数が出てくるよね。……これが本質なんですね。今回注目したいこと」
データの個数を $N$ とすると、およそ $N^2$ に比例した手間がかかる。これが「 $N^2$ のアルゴリズム」の正体であり、エンジニアが「ダサい」と呼ぶ理由です。
コンピュータ科学の最重要単語「オーダー」の恐怖
この「データの数が増えたときに、どれくらい計算の手間が増えるか」という勢いを示す指標を、「オーダー（ $O$ 記法）」と呼びます。
選択ソートのオーダーは $O(N^2)$ と表現します。ここで面白いのは、コンピュータ科学者が細かい係数や端数をバッサリと切り捨て、「一番影響が大きい部分」だけを見ることです。
「データの個数がN個の時、計算回数はN2乗ぐらいになるよねっていうのがオーダー」
なぜ係数を無視するのか。それは $N$ が大きくなったとき、 $N^2$ の増加率が他の全てを圧倒するからです。
例えば、漫画が10巻なら $N^2$ は100。まだ人間でも余裕です。
しかし、漫画が1000巻になれば $N^2$ は100万。
もしこれがWebサービスのように100万人のユーザーデータを扱う $N=1,000,000$ になれば、 $N^2$ は「1兆」という天文学的な数字に膨れ上がります。
正直、データが数件しかないなら、ダサいと言われた選択ソートの方が速いこともあります。仕組みが単純な分、準備運動がいらないからです。しかし、プロの現場で扱うデータ量は常に増え続けます。データの増加に対して、手間が爆発的に増えてしまう $O(N^2)$ を選ぶことは、将来的な「処理のパンク」を予約するようなものなのです。
1兆回が2000万回に？ 直感を捨てる勇気が生む「 $\log$ の劇的効率」
では、もっと賢い方法、つまり「デキる」アルゴリズムとはどのようなものでしょうか。
並べ替え（ソート）の世界において、現在最善とされているオーダーは $O(N \log N)$ です。ここで、多くの人が高校数学でアレルギーを起こしたであろう「 $\log$ （ログ）」が、最強の武器として再登場します。
「正直、 $\log$ なんて忘れたよという人も多いでしょう。でも、アルゴリズムの世界では『半分に分け続けると最強になる魔法の杖』だとだけ覚えておけばいいんです」
$\log$ の最大の特徴は、 $N$ が大きくなっても数値が驚くほど増えないことです。
例えば、データの数が100から1000へと10倍になっても、 $\log$ の部分はほんのわずかしか増えません。
具体的に比較してみましょう。データが100万個あるとき。
- $O(N^2)$ の場合： 1,000,000 × 1,000,000 ＝ 1兆回
- $O(N \log N)$ の場合： 1,000,000 × 20 ＝ 2,000万回 （※ $\log_2 N$ で計算）
その差は実に5万倍。 $O(N^2)$ ならコンピュータが一生かかっても終わらないような作業が、 $O(N \log N)$ ならお昼休みが終わる前に完了してしまう。この圧倒的な差を生み出すのが、「クイックソート」や「マージソート」といった、全体を効率よく分割して処理するアルゴリズムです。
1巻ずつ順番に確定させるという「直感」を捨て、全体を半分、また半分と「分割」して統治する。この数学的なアプローチこそが、退屈な作業の裏側に潜む「巧妙なトリック」なのです。
巧妙なトリック、心地よい驚きを体感せよ
「良いアルゴリズムというものは、巧妙なトリック、うん。こころよい驚きを感じることができるものである」
コンピュータ科学の醍醐味は、単にコードを書くことではなく、こうした「賢い解法」に出会ったときの感動にあります。
私たちが日常生活で「気合」や「丁寧さ」でカバーしようとしている作業の多くは、実は手順を変えるだけでオーダーを劇的に落とせる可能性があります。
例えば、大量の書類から特定の1枚を探すとき、端からめくっていくのは $O(N)$ です。しかし、もし書類が五十音順に並んでいるなら、真ん中をめくって範囲を絞り込む「二分探索」を使えば、オーダーは一気に $O(\log N)$ まで落ちます。100万枚の書類があっても、わずか20回めくるだけで目的の1枚に辿り着ける計算です。
闇雲に努力するのではなく、まずその問題に対する「解法（アルゴリズム）」を疑ってみる。その視点を持つだけで、仕事の生産性は文字通り「次元が変わる」ほど向上します。
まとめ
この記事をまとめると…
- アルゴリズムの真の評価は、PCのスペックに依存しない「計算回数」の増加率で決まる。
- 1つずつ順番に確定させる「選択ソート」は $O(N^2)$ であり、データが増えると指数関数的に「ダサい努力」へと変わる。
- 「オーダー（ $O$ 記法）」は、ビジネスにおける「スケールアップへの耐性」を示す指標である。
- $\log$ を活用した $O(N \log N)$ のアルゴリズムは、直感に反するが、劇的な効率化をもたらす「知性の結晶」である。
次にあなたが膨大なエクセルデータや、あるいは家の掃除に立ち向かうとき、「この作業のオーダーを落とすには？」と自分に問いかけてみてください。
その瞬間、あなたは単なる「作業者」から、世界を効率化する「コンピュータ科学者」への第一歩を踏み出しているはずです。心地よい驚きは、常にあなたのすぐそばにあるのですから。
配信元情報
番組名：ゆるコンピュータ科学ラジオ
タイトル：あなたのマンガ並び替え方法はダサい。オーダーがダサい【アルゴリズム2】#2
配信日：2022-01-11
