計算量O記法入門_最強効率O(log_n)とは

今回のテーマはプログラムの効率の良さですね。どんなに賢いアルゴリズムでも、処理に100年かかっては、まあ意味がないですよね。 ええ、まさに。そこが重要なんです。プログラムが動くっていうことと、プログラムが効率的に動くっていうのは、全く別の話で。 はい。あの、事前に共有いただいた資料にあった「100万件のバラバラな名簿から特定の1人を探す」っていう例、あれがこの問題を考えるのにもう完璧な出発点かなと。 なるほど。じゃあ、その「計算量」という考え方を紐解いていきましょうか。これがなぜ一流のエンジニアにとって重要なのか、その核心に迫っていきたいと思います。 はい、ぜひ。では、まず一番直感的な方法から。資料にもあった通り、名簿を上から一個一個見ていくやり方ですよね。 ええ。これだと、データがN件あれば最悪の場合N回の手間がかかる。そうですね。これが、えっと、ON…オーダーN、でしたっけ？ その通りです。ここで大事なのがまさにその「計算量」という考え方でして、データが増えたときにどれくらい手間が増えるか、っていう、まあ指標なんですね。 ONっていうのは、その増え方がデータ量にこう、比例しますよ、ということです。なるほど。データが2倍になれば手間も2倍。シンプルですね。 ええ、非常に素直な関係です。でもそれだと100万件の名簿だと最悪100万回かかるわけじゃないですか。そうなんです。ちょっと気が遠くなりますよね。 そこで、もっと賢い方法として資料で挙げられていたのが「二分探索」。はいはい。あらかじめ名前が順番に並んでいれば、辞書みたいに半分に、また半分にと絞り込んで探せると。 ええ、その通りです。これ、魔法みたいに聞こえるかもしれませんけど、すごく合理的な仕組みで。ほう。まずリストのど真ん中を見るんです。で、探してる名前がそれより前か後か判断する。 それだけで、半分はもう探す必要がなくなりますよね。確かに。で、残った後半のさらに真ん中を見る。これを繰り返していくんです。 へえー、どんどん絞り込んでいくんですね。それで実際どれくらい早くなるんですか？ここが本当に面白いところなんですけど、この方法は「オーダーログN」、O(log N)って呼ばれてまして。 オーダーログN。ええ。100万件のデータでも、なんとたった20回程度で探し出せるんですよ。へっ？え、20回ですか？100万件を？ そうなんです。たった20回。それは信じられないですね。100万回と20回じゃ、もう全然なんていうか、別の次元の話じゃないですか。 まさに。この差こそがアルゴリズムの効率性を学ぶ本質なんで。同じ結果を出す処理でも、計算量が違うだけで現実世界で使い物になるかどうかが決まってしまう。 なるほどなあ。例えば、皆さんが普段使ってる検索エンジンとかで、ONみたいな処理が走ってたら、結果が出るまでにもう数分とか、下手したら数時間かかっちゃうかもしれない。 うわー、それは困りますね。O(log N)みたいな効率的なアルゴリズムがあるからこそ、一瞬で済むわけです。そういうことだったんですね。 では逆に、プログラマーが最も恐れる「地雷」として紹介されてたのが、えっと、ON二乗、オーダーN二乗。ああ、来ましたね。 これはなぜそんなに怖いんですか？これをですね、初心者がうっかり作ってしまう「時限爆弾」なんて呼ばれたりもします。時限爆弾？ ええ。例えば、総当たりで2つのデータを組み合わせるみたいな二重ループ処理で発生しやすいんです。データが増えると処理時間がもう爆発的に長くなってしまう。 「爆発的」ですか。はい。データが100件なら1万回、1000件なら100万回。手間が二乗で増えていくので。 私も若い頃に、テストデータが少ないときは動いたのに、本番データ入れたらシステムが固まって冷や汗をかいた経験がありますよ。うわあ、それは生々しい。 では、今日のポイントをまとめましょうか。はい。まず「計算量」というのは、データが増えたときに処理の手間がどう増えるかを示す指標。そうですね。 そして「O（オーダー）」はその増え方の形をシンプルに表す記号だと。ええ、その通りです。ONはデータ量に比例、O(log N)は非常に効率的、そしてON^2はデータが増えると急激に遅くなる。 これを覚えておくだけでも、プログラムの見え方がだいぶ変わりそうですね。まさに。最後に1つ、思考を深める問いを投げかけてみてもいいですが？ あ、ぜひお願いします。今回は処理にかかる「時間」の計算量に注目しましたよね。はい。では、プログラムが使うメモリー量、つまり「空間計算量」についてはどうでしょうか。 もし少し時間はかかるけれど、メモリーの使用量を劇的に減らせるアルゴリズムがあったとしたら、あなたどちらを選びますか？うーん、時間かメモリーか。 ええ。その判断基準、そのトレードオフを考えることが、エンジニアリングの次のステップになっていくんです。