同じ問題を解くアルゴリズムでも、データが増えたときの速さは大きく変わります。その「効率」をざっくり表すのがO記法(オーダー記法)。読み方と代表的な計算量を、身近なたとえで整理しましょう。
星見 めい
計算量って、O(n)とかO(n²)とか書いてあるやつだよね? 記号だけ見るとなんか難しそうじゃん。
紫垣 こはる 先生
見た目ほど難しくないのよ。
これは計算量を表すO記法(オーダー記法)ね。
入力の量nが増えたとき、処理の回数や時間がどんなペースで増えるかを示すの。
小夜川 ほのか
ペース…ですかぁ? どういうことなのぉ?
紫垣 こはる 先生
たとえばクラス全員のテストを採点するとき、人数が2倍になれば手間も2倍。
これがO(n)、人数に比例するタイプね。
でも「全員の点数を一人ずつ全員と比べる」みたいな作業だと、人数が2倍で手間は4倍になっちゃうの。
星見 めい
あー、総当たりってやつね。
確かに人数増えると一気にしんどくなるやつだ。
蜂谷 まこと
その総当たりがO(n²)です。
補足すると、O記法では一番影響の大きい項だけを見ます。
だから3n²+5n+2のような式でも、nが大きくなれば二乗の項が支配的になるので、まとめてO(n²)と書くんですね。
小夜川 ほのか
細かい係数や小さい項は気にしないんですねぇ。
ざっくり見るのが大事なのぉ。
蜂谷 まこと
はい。
代表的なものを速い順に並べると O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) です。
左にあるほど、データが増えても処理がゆるやかにしか増えません。
星見 めい
左が優秀ってことね。
でもこの並び、どれくらい差があるのかピンとこないなあ。
紫垣 こはる 先生
数で見ると衝撃的よ。
n=1000のとき、O(1)はたった1回、O(log n)はおよそ10回、O(n)は1000回、O(n²)はなんと100万回。
同じ仕事でもアルゴリズム次第でこれだけ違うの。
星見 めい
マジか、1回と100万回って差ありすぎでしょ!
小夜川 ほのか
それぞれ、どんな身近な例があるんですかぁ?
蜂谷 まこと
O(1)は定数時間で、配列の番号を指定して取り出すアクセスや、ハッシュによる検索ですね。
O(log n)は二分探索。
O(n)は先頭から順に見る線形探索です。
紫垣 こはる 先生
二分探索のイメージは辞書引きね。
真ん中を開いて、目的の語が前か後ろかで半分に絞る。
これを繰り返すから、1000語でも10回くらいで見つかるのよ。
小夜川 ほのか
あぁ、だから10回くらいなんですねぇ。
半分ずつ減るとあっという間なのぉ。
蜂谷 まこと
続きを補足すると、O(n log n)はマージソートやクイックソートなどの高速な並べ替え、O(n²)はバブルソート、O(2^n)は全部の組み合わせを試す全探索です。
2^nはnが少し増えただけで爆発的に増えるので要注意ですね。
星見 めい
ところでさっきから処理の回数の話ばっかだけど、メモリのことは考えなくていいの?
紫垣 こはる 先生
いい着眼点ね。
実は計算量には2種類あるの。
処理時間を見る時間計算量と、使うメモリ量を見る空間計算量よ。
星見 めい
へえ。
じゃあその2つって、片方を良くするともう片方が悪くなったりする?
蜂谷 まこと
はい、トレードオフになりがちです。
例えば計算結果を覚えておくメモ化は、メモリを多めに使う代わりに時間を大きく節約できます。
小夜川 ほのか
速さとメモリは、どっちも欲張りにくいんですねぇ…。
紫垣 こはる 先生
そうなのよ。
だからビッグデータの時代は計算量がますます大事。
たとえば1000万件のデータにO(n²)を使うと処理は約100兆回。
現実的な時間では終わらないの。
だからスケーラビリティを考えてアルゴリズムを選ぶ必要があるわ。
星見 めい
アルゴリズムの選び方ひとつで、終わるか終わらないかまで変わるんだ。
記号、ちゃんと読めるようになっとくわ!
紫垣 こはる 先生
ふふ、その意気よ。
まとめると、O記法はデータが増えたときの増え方を表す目安。
速い順は O(1)<O(log n)<O(n)<O(n log n)<O(n²)<O(2^n)。
そして時間と空間の両面で考える。
この3点を押さえれば計算量は得点源になるわ。
確認クイズ
次のO記法のうち、入力サイズnが大きくなったときに最も処理量が少なく済む(最も高速な)ものはどれか。
- O(n²)
- O(n log n)
- O(log n)
- O(n)
こたえを見る
正解: 3. O(log n)
正解はO(log n)。計算量の速い順は O(1) < O(log n) < O(n) < O(n log n) < O(n²) であり、選択肢の中ではO(log n)が最も増え方がゆるやか。O(n)は比例、O(n log n)はそれより大きく、O(n²)は二乗で増えるため最も遅い。
