計算量は、入力の大きさに対して必要な処理量やメモリ量がどう増えるかを考える指標です。秒数そのものと区別し、どの条件で評価しているかを確認しましょう。
1．O記法は増え方の上界を表す
O記法は、入力が十分大きいときの増え方の上界を表します。入力の大きさをnとし、最悪時・平均時など、評価対象も明示します。O(1)は入力が増えても一定の範囲で、処理が必ず1回だけという意味ではありません。
2．代表例と前提を整理する
| 目安 | 代表的な例と条件 |
|---|---|
| O(1) | ランダムアクセスできる配列の要素参照 |
| O(log n) | 整列済みの範囲を半分ずつ絞る二分探索の最悪時 |
| O(n) | 全要素を順に調べる線形探索の最悪時 |
| O(n log n) | マージソートなど。クイックソートは通常の平均時 |
| O(n²) | 二重ループなど。クイックソートも最悪時は二乗となり得る |
ループが2つあるだけで常にO(n²)とは限りません。各ループの回数や、入れ子か順番に実行するかを確認します。O(log n)と書く場合、底が異なる定数倍は通常の漸近評価では区別しません。
3．実際の速さを断定しない
入力が小さいときの定数の負担や、ハードウェア、データの配置でも実行時間は変わります。「O(1)ならどんな条件でも最速」とは断定できません。時間計算量と空間計算量も別に評価します。
理解を確かめる確認問題
整列済みデータで探索範囲を毎回半分に絞る二分探索の、最悪時の計算量はどれでしょうか。
ア：O(1) イ：O(log n) ウ：O(n²)
解答・解説を見る
正解はイです。範囲を半分ずつ絞るため、必要な段階数は対数的に増えます。
まとめ：入力・処理回数・評価条件を確認する
単語の速い・遅いだけで覚えず、入力が増えたときの処理を追いましょう。
コメント