計算量は『データが増えたときの実行時間の伸び方』を抽象化した概念。O(1) ・O(log n) ・O(n) ・O(n log n) ・O(n²) ・O(2^n) の感覚をつかみましょう。
砂原 ニコ
O(n) と O(n²) ってどれくらい違うの?
緒方 ナオミ 先生
n=1000 なら O(n)=1000ステップ、O(n²)=100万ステップ。
1000倍違うわ。
オーダー記法 は『最も影響の大きい項』だけを残して評価するの。
鳴海 理央
O(log n) は対数なので非常に緩やかに増えます。
n=1,000,000 でも約20。
二分探索の強みです。
時間計算量 と 空間計算量 は別概念で、メモリと速度のトレードオフを意識する必要があります。
藤咲 まりあ
O(2^n) って指数だから、すっごい増え方なんですよねぇ?
鳴海 理央
そうです。
n=30 でも10億超。
これに該当する問題が NP困難の領域で、現実的な時間で厳密解を求められない代表例です。
緒方 ナオミ 先生
AP では関数の合成 (T(n)=n^2 + 100n + 5 → O(n²)) と、再帰式から計算量を導く問題が頻出。
マスター定理は深入り不要だけど、漸化式を解く感覚は持っておきましょう。
確認クイズ
次のうち、計算量が最も大きい (大きなオーダーの) ものはどれか。
- O(n log n)
- O(n²)
- O(n³)
- O(2^n)
こたえを見る
正解: 4. O(2^n)
指数 O(2^n) は最も急速に増加します。n=20 で約100万、n=30 で約10億、n=40 で約1兆。NP困難な問題はこのオーダーが基本で、現実時間で厳密解を求めるのが困難です。