計算量とは（全体像）
計算量とは、アルゴリズムが、どれくらいの「時間」や「メモリ」を使うかを、データの数（n）を使って表した指標のことだ。これをビッグオー記法（O記法）で、O(n)やO(n²)のように書く。
なぜ大事かというと、データが多くなると、アルゴリズムのやり方（オーダー）の違いが、大きく効いてくるから。速いやり方を選べば、同じ仕事でも、ずっと短い時間で終わる。
代表的なオーダーを、速い順に並べると、こうなる。
O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²)
右にいくほど、データが増えたときに遅くなる。
詳しく：オーダーの順と、具体例
ここが心臓部。代表的なオーダーを表で押さえよう。
主なオーダー（速い順）
| オーダー | 速さ | 例 |
|---|---|---|
| O(1) | いちばん速い（一定） | 配列の番号アクセス |
| O(log n) | 速い | 2分探索 |
| O(n) | ふつう | 線形探索 |
| O(n log n) | やや遅い | クイック／マージソート |
| O(n²) | 遅い | バブルソート |
このように、O(1)がいちばん速く、右にいくほど遅くなる。たとえば、2分探索はO(log n)で速く、バブルソートはO(n²)で遅い。
ここで一番のポイント。データが多いほど、この差が大きく効いてくる。少ないデータなら、どのやり方でも大差ないが、データが何百万件にもなると、O(n²)のやり方は、現実的でないほど時間がかかる。「データが多くても、やり方による差は小さい」と思い込むと誤りになる。なお、O記法では、定数倍（2倍など）は無視して、おおまかな増え方で比べる。
わかりやすく言い換えると
身近なたとえで整理しよう。
計算量は、「データが増えたとき、どれくらい時間が増えるかの目安」のイメージ。O(n²)なら、データが10倍で、時間は約100倍だ。
オーダーの順は、「O(1)がいちばん速く、O(n²)は遅い」こと。要するに、右にいくほど、データが増えたときに苦しくなる。つまり、速いやり方を選ぶほど有利だ。
「データが多いと差が効く」というのは、少しのデータなら大差ないが、大量になると、速いやり方が圧倒的に有利だということだ。
試験のツボ
🔴 一番出る：オーダーの順
①速い順は、O(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)
②右にいくほど、データが増えたときに遅くなる
🔴 次に出る：具体例
①2分探索＝O(log n)、線形探索＝O(n)
②ソート（クイック／マージ）＝O(n log n)、バブルソート＝O(n²)
🟡 押さえると安定：データが多いと差が効く
①データが多いほど、オーダーの差が大きく効く
②定数倍（2倍など）は無視して、おおまかに比べる
よくある間違い
①「データが多くても、アルゴリズムのやり方による差は小さい」→ ✗ データが多いほど、オーダーの差が大きく効く。O(n²)は現実的でないほど遅くなることも。
②「O(1)よりO(n²)のほうが速い」→ ✗ O(1)がいちばん速く、O(n²)は遅い。右にいくほど遅くなる。
③「O(2n)とO(n)は、まったく別のオーダーだ」→ ✗ 定数倍（2倍など）は無視するので、O(2n)もO(n)も同じオーダー。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（計算量の正体）
計算量（ビッグオー記法）に関する次の記述のうち、最も適切なものはどれか。
- 社員の出退勤を記録して、毎月の給与を計算するためのしくみである
- アルゴリズムの時間やメモリを、データの数nで表した指標である
- 取引先へ毎月の請求書を郵送する、決まった事務作業のことを指す
- 完成したシステムを宣伝して、より多く売るための広告活動である
解答は 2 だぱん。
計算量は、アルゴリズムの時間やメモリを、データの数nで表した指標なんだぱん。ビッグオー記法で、O(n)のように書くんだぱん。
選択肢1は給与計算、選択肢3は請求書の事務、選択肢4は広告で、どれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のしくみではない |
| 2 | ✓ | 時間やメモリをnで表す指標で正しい |
| 3 | ✗ | 請求書の事務の話 |
| 4 | ✗ | 広告活動ではない |
オリジナル問題2（オーダーの順）
オーダーの速さの順として、最も適切なものはどれか。
- O(n²)がいちばん速く、O(1)がいちばん遅いとされているものだ
- 社員の給与の計算しだいで、速さの順が決まるとされているものだ
- 取引先への請求書の枚数しだいで、速さの順が決まるとされている
- O(1)がいちばん速く、O(n²)は遅い（右にいくほど遅くなる）
解答は 4 だぱん。
速さの順は、O(1)がいちばん速く、O(n²)は遅い（右にいくほど遅くなる）んだぱん。O(1)＜O(log n)＜O(n)＜O(n²)の順だぱん。
選択肢1は順が逆、選択肢2は給与、選択肢3は請求書で誤りだぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | O(1)が速く、順が逆 |
| 2 | ✗ | 給与計算で決まるのではない |
| 3 | ✗ | 請求書の枚数で決まるのではない |
| 4 | ✓ | O(1)が速くO(n²)は遅いで正しい |
オリジナル問題3（データが多いと差が効く）
データの量とオーダーの関係に関する次の記述のうち、最も適切なものはどれか。
- 社員の給与を計算するときだけ、オーダーの差が出るとされている
- 取引先へ請求書を郵送するときだけ、オーダーの差が出るとされる
- データが多いほど、オーダーの差が大きく効いてくるものである
- データが多くても、オーダーによる差はほとんど出ないとされる
解答は 3 だぱん。
データが多いほど、オーダーの差が大きく効いてくるんだぱん。データが大量だと、O(n²)は現実的でないほど遅くなることもあるんだぱん。
選択肢1の給与、選択肢2の請求書、選択肢4の「差はほとんど出ない」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のときだけではない |
| 2 | ✗ | 請求書のときだけではない |
| 3 | ✓ | データが多いほど差が効くで正しい |
| 4 | ✗ | データが多いと差は大きくなる |
まとめ
押さえどころ
- 🔴 計算量（ビッグオー記法） ＝ アルゴリズムの時間やメモリを、データの数nで表した指標。
- 🔴 オーダーの順 ＝ 速い順に O(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)。右にいくほど遅い。
- 🟡 データが多いと差が効く ＝ データが多いほど、オーダーの差が大きく効く。定数倍は無視して比べる。
次に学ぶ
- アルゴリズム ── 問題を解く手順。計算量は、その効率（速さ）の目安。
- ビッグオー記法 ── O(n)などで計算量を表す書き方。アルゴリズムの速さを比べる物差し。
執筆: SikakuQuest編集部