計算量とは（全体像）
計算量は、「入力データが増えると、処理時間がどんなふうに増えるか」を表す尺度。実際の秒数ではなく、増え方の形で評価するのがポイントだ。
なぜ秒数で測らないかというと、パソコンの速さや言語で実際の時間は変わってしまうから。「データが2倍になったら時間も2倍か、4倍か」という増え方なら、機械によらず比べられる。
評価には3つの記法がある。
- Big-O … いちばん時間がかかる場合（上限・最悪）の目安。最もよく使う。
- Ω（オメガ） … いちばん速い場合（下限・最良）の目安。
- Θ（シータ） … 上限と下限が一致するときの、ぴったりの目安。
詳しく：オーダーの順番と漸近評価だけ覚えれば戦える
ここが記事の心臓部。まずはオーダー（速さのクラス）の順番。
オーダーの順番（左ほど速い）
| オーダー | 速さ | 例 |
|---|---|---|
| O(1) | 一番速い | 配列の番号アクセス |
| O(log n) | とても速い | 2分探索 |
| O(n) | ふつう | 線形探索 |
| O(n log n) | 速いソート | マージ・クイック |
| O(n²) | 遅い | バブルソート |
| O(2^n) | とても遅い | 全部の組合せを試す |
この順番は最頻出。「O(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)＜O(2^n)」を丸ごと覚える。右にいくほど、データが増えたときの遅くなり方が激しい。
次に、計算量の大事な性質（漸近評価）。
計算量の性質
| 性質 | 内容 |
|---|---|
| 定数倍は無視 | 3nも100nも同じO(n) |
| 低い項は無視 | n²＋nは、いちばん大きいn²だけ見てO(n²) |
計算量は「データがうんと多くなったときの増え方」を見るので、定数倍（3倍・100倍）や小さい項は無視する。だから3nも100nも同じO(n)。「O(2n)とO(n)は別もの」と思うのは誤りだ。
わかりやすく言い換えると
要するに、計算量は「データが増えたときの、時間の増え方のクセ」だ。
①O(n) … データが10倍になると、時間も約10倍
②O(n²) … データが10倍になると、時間は約100倍（一気に遅くなる）
③O(log n) … データが10倍になっても、時間はほんの少ししか増えない（とても速い）
つまり、実際の秒数ではなく「増え方の形」で比べるから、機械が違っても公平に速さを比較できる、というわけだね。
試験のツボ
🔴 一番出る：オーダーの順番
①O(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)＜O(2^n)
②右にいくほどデータ増加で激しく遅くなる
🔴 次に出る：3記法の意味
①Big-O＝上限（最悪の目安）
②Ω＝下限（最良）、Θ＝上下一致のぴったりの目安
🟡 押さえると安定：漸近評価の性質
①定数倍は無視（3nも100nもO(n)）
②低い項は無視（n²＋nはO(n²)）
よくある間違い
①「O(2n)とO(n)は別のクラスである」→ ✗ 定数倍は無視するので、O(2n)もO(n)も同じクラス。
②「計算量は実際の実行秒数そのものを表す」→ ✗ 秒数ではなく「データが増えたときの増え方」を表す（漸近評価）。
③「Big-Oは最良の場合（下限）を表す」→ ✗ Big-Oは上限（最悪の目安）。下限はΩ。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（オーダーの順番）
計算量のオーダーの大小に関する次の記述のうち、正しいものはどれか。
- O(n²)はO(log n)より速く、データが増えても遅くなりにくいオーダーである
- O(log n)はO(n)より速く、O(n²)はO(n log n)より遅い
- すべてのオーダーは同じ速さで、データが増えても遅くなり方は変わらない
- O(2^n)はO(1)より速く、最も効率の良いオーダーであるとされている
解答は 2 だよ。
オーダーはO(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)＜O(2^n)の順で、右にいくほど遅くなるんだ。この順番を丸ごと覚えてね。
選択肢1はO(n²)を「速い」とする誤り。選択肢3は「同じ速さ」が誤り。選択肢4はO(2^n)を「最も速い」とする誤り（最も遅い側）だよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | O(n²)はO(log n)より遅い |
| 2 | ✓ | log nはnより速く、n²はn log nより遅い |
| 3 | ✗ | オーダーで遅くなり方が違う |
| 4 | ✗ | O(2^n)は最も遅い側 |
オリジナル問題2（3記法）
計算量の記法に関する次の記述のうち、正しいものはどれか。
- Big-Oは下限（最良）、Ωは上限（最悪）を表し、ΘはBig-Oと同じ意味である
- Big-OもΩもΘもまったく同じ意味で、どれを使っても違いはないとされる
- Big-Oは実際の秒数を、Ωは使うメモリの量を直接表す記法のことである
- Big-Oは上限（最悪）、Ωは下限（最良）、Θは上下が一致するぴったりの目安だ
解答は 4 だよ。
Big-Oは上限（最悪）、Ωは下限（最良）、Θは上下が一致するぴったりの目安なんだ。ふだんいちばん使うのはBig-Oだよ。
選択肢1はBig-OとΩが逆。選択肢2は「同じ意味」が誤り。選択肢3は「秒数・メモリを直接表す」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | Big-Oは上限・Ωは下限（逆） |
| 2 | ✗ | 3記法は意味が異なる |
| 3 | ✗ | 秒数そのものではない |
| 4 | ✓ | Big-O上限・Ω下限・Θぴったり |
オリジナル問題3（漸近評価）
計算量の漸近評価に関する次の記述のうち、正しいものはどれか。
- 定数倍は無視するため、3nも100nも同じO(n)のクラスに分類される
- 定数倍は重要なので、3nはO(3n)、100nはO(100n)と区別して書く
- 低い項のほうを重視するため、n²＋nはO(n)に分類されるものである
- 計算量はデータの個数とは無関係に、つねに一定の値になるものである
解答は 1 だよ。
計算量は定数倍を無視するから、3nも100nも同じO(n)なんだ。データがうんと多いときの増え方を見るので、何倍かは気にしないんだよ。
選択肢2は「定数倍を区別」が誤り。選択肢3は「低い項を重視」が誤り（大きいn²を見る）。選択肢4は「個数と無関係」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 定数倍は無視で同じO(n) |
| 2 | ✗ | 定数倍は区別しない |
| 3 | ✗ | 大きいn²だけ見てO(n²) |
| 4 | ✗ | 個数で増え方が変わる |
まとめ
押さえどころ
- 🔴 オーダーの順番 ＝ O(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)＜O(2^n)。右ほど遅い。
- 🔴 3記法 ＝ Big-Oは上限（最悪）、Ωは下限（最良）、Θは上下一致のぴったり。
- 🟡 漸近評価 ＝ 定数倍は無視（3nも100nもO(n)）、低い項も無視（n²＋nはO(n²)）。
次に学ぶ
- ソートアルゴリズム ── O(n²)とO(n log n)の差が実感できる代表例。計算量の順番がそのまま速さの違いになる。
- 探索アルゴリズム（BFS・DFS・2分） ── O(log n)の2分探索やO(1)のハッシュ探索が登場。オーダーの感覚が深まる。
執筆: SikakuQuest編集部