プログラムの速さを測る方法：計算量とO記法

皆さんこんにちは。毎日何気なく使ってるアプリとかウェブサイトありますよね。あれって裏側ではものすごい数のプログラムが動いてるんです。 じゃあ、どうやったらあれをサクサク快適に動かせるんでしょうか？今日はね、プログラマーが使ってる速さのものさし、その秘密にちょっと迫ってみようと思います。 さてちょっと想像してみてください。いきなりですけどね。もし皆さんの目の前に100万人もの名前がずらっと書かれた、とてつもなく分厚い名簿があったとします。 で、この中からたった1人の名前をできるだけ早く見つけてください、って頼まれたら、さあどうしますか？ まあ多分多くの人が、一番上から順番に一つずつコツコツチェックしていく、そんな方法を思い浮かべますよね。もちろんそれでもいつかは見つかります。 でもそれって、一番賢いやり方なんでしょうか？もしもっとこう、劇的に時間を短くできる方法があるとしたら、知りたくないですか？ さあ、問題はこのリストがもっともっと、とんでもなく大きくなったときなんです。データが増えれば増えるほど、探すのにかかる時間もそりゃあもう、どんどん長くなっちゃいますよね。 この、データの量とかかる時間の関係。これをどうやって測るのか。実はそれが今日の話の肝になるわけです。 はい、というわけで今回はこんな流れで進めていきます。まずあの100万人の中から探す話。次にその手間を測るってどういうことか。 そしてそれを表す魔法の記号、オーダーについて。で、最速と最悪のケースを見て、最後に、なぜこれが一流のエンジニアに必要なのか、という話に繋げていきます。 はい、では早速最初のセクションから見ていきましょう。あの100万人のリストから名前を探し出す、全く違う2つのやり方を比べてみます。 はい、まず一つ目が「線形探索」。これはさっきみんなで考えた、上から一個ずつしらみつぶしに見ていく、まあシンプルでわかりやすい方法ですよね。 で、もう一つが「二分探索」。これはね、リストがちゃんと例えば50音順みたいに並んでるときにだけ使える、すっごく賢い方法なんです。 何をするかっていうと、まずいきなりリストのど真ん中を開くんですよ。で、探してる名前がその真ん中の名前より前にあるか後ろにあるかを見る。 それだけで探す範囲が一気に半分になるじゃないですか。これをどんどん繰り返していくわけです。 じゃあここでクイズです。100万件のリストで、さっきのシンプルな線形探索をやった場合、最悪のケースだと何回チェックしないといけないと思いますか？ はい、答えはそのまんま。100万回です。そりゃそうですよね。もし探してる名前がリストの最後にあったら、結局全部見る羽目になっちゃいますから。 じゃあそれに対してあの賢いやり方、二分探索だとどうなると思います？ これ信じられますかね。なんとたったの約20回で見つかっちゃうんです。100万回と20回ですよ。 この差、凄くないですか？まさにやり方、つまりアルゴリズムの力ってやつですよね。もう驚異的です。 じゃあこのとんでもない効率の差をプログラマーたちはどうやってちゃんと表現しているんでしょうか。次のセクションでは、この違いをスマートに表すための考え方を見ていきましょう。 そこで出てくるのが、この「計算量」っていう言葉なんです。これ、簡単に言うと、データが増えたときに処理の手間がどれだけのペースで増えていくのかを示す指標。 まあ燃費みたいなものだと思ってもらうと分かりやすいかもしれません。 で、ここからが面白いんです。エンジニアってこの計算量について話すとき、ある特別な、まあ共通言語みたいなものを使うんです。ほとんど合言葉ですね。 それがこれ。「O（オー）記法」、または「ビッグ・オー（Big O）記法」と呼ばれるものです。どんなに複雑なプログラムの効率もこの「O」と括弧を使えば、 たった数文字でピタッと表現できちゃう。まさに魔法の記号ですよね。 じゃあさっきの例で見てみましょうか。まず、データが増えた分だけそのまんま手間も増える線形探索。これは O(n)、オーダー・エヌと書きます。 このnっていうのはデータ数のことですね。データが2倍になれば時間も2倍。シンプルです。 一方あのめちゃくちゃ速かった二分探索は、O(log n)、オーダー・ログ・エヌと書きます。この log n が本当に凄くて、 データが倍になっても手間はほんのちょっとしか増えないんです。さっきの例で言うと、100万件のデータが200万件に増えても、 チェック回数は20回が21回になるだけ。このとんでもない効率の良さこそが、あの100万回と20回の差の正体だったわけですね。 O(n) とか O(log n) っていうのはまあよく出てくるんです。でもこの計算量の世界には、はっきりとした天国と地獄があるんですよ。 その両極端を見てみると、なんでエンジニアがこの話をこんなに気にするのか、その理由がよく分かると思います。 まずは天国から。それが O(1)、オーダー1。これはもう最強です。データが100万件だろうが1億件だろうが、かかる時間が全く変わらない。 いつだって一瞬で終わるっていう、まさに理想の処理です。 そして、その正反対にある地獄。プログラマーたちが絶対に踏んではいけない地雷って言われてるのがこれ。O(n²)、オーダーnの2乗です。 この表をちょっと見てください。O(n) と O(n²) で手間がどれくらい違うか、一目瞭然ですよね。 データが10個のときはまあ10と100で、そんなに変わらないかなって思うじゃないですか。でも、データが1000個になった瞬間を見てください。 O(n) は1000回ですけど、O(n²) はなんと100万回！もう爆発的に手間が増えちゃってるんです。 これが地雷って呼ばれる理由なんですよ。うっかり作っちゃうととんでもないことになります。 つまりですね、これって単なる難しい理論の話じゃないんです。本当に動く、使えるプログラムを作るうえで、優れたエンジニアとそうでない人を分ける、めちゃくちゃ実践的なスキルなんですよ。 ただ動くプログラムを作るだけじゃなくて、データが将来どれだけ増えても、ちゃんとサクサク動き続ける、そういう効率のいいプログラムを作れるかどうかが重要なんです。 この計算量を意識できるかどうかが、まさに一流のエンジニアになれるかどうかの分かれ道、と言ってもいいかもしれません。 はい、というわけで今日のポイントをさっとおさらいしましょう。まず計算量。これはデータが増えたときの手間の増え方のことですね。 そして O記法。これはその計算量を表すための共通言語。 特に覚えておいてほしいのは、理想的な O(1)、めちゃくちゃ速い O(log n)、普通な感じの O(n)、そして絶対に避けたい危険な O(n²)。 この感覚、ぜひ掴んでおいてください。 さあ、この新しいものさしを手に入れた皆さん、ぜひちょっと考えてみてほしいんです。 今皆さんが書いているコード、あるいはこれから書くコード。その計算量って、一体どれくらいなんでしょうか。 この「効率」っていう視点を一つ持つだけで、皆さんが作るプログラムは間違いなく次のレベルに進めるはずです。