計算量（computational complexity）

分類

テクノロジ系 アルゴリズムとプログラミング

出る試験

基本情報応用情報

重要度

★★★☆☆

もう少し詳しい説明

計算量は、データの件数が増えたときに、処理時間がどう伸びるかを表したものです。

ここで大事なのは、「何秒かかるか」ではないということです。同じ処理でも、速いパソコンで動かせば短く済みます。

使ったパソコンの性能で変わってしまう秒数を比べても、やり方そのものの善し悪しは分かりません。 速いパソコンで動かした下手なやり方のほうが、遅いパソコンで動かした上手なやり方より短く終わる、ということが起きるからです。

そこで秒数ではなく、件数が増えたときの伸び方だけを取り出して比べます。

O記法：伸び方だけを書く

計算量は O記法（オーダ記法）で書きます。O(n) のように、カッコの中に伸び方を書きます。n はデータの件数です。

件数を100倍にしたときで、そろえて比べます。

細かい係数は書きません。「n の2乗に3を掛けて5を足す」（3n² ＋ 5）という処理でも、O(n²) とだけ書きます。

ここが引っかかりやすいので、理由を2つに分けます。どちらも「3 や 5 は n が変わっても 3 と 5 のままなのに、n² だけがいくらでも大きくなる」という話です。

① 足している 5 は、すぐ無視できる大きさになる

n を増やしながら、全体に占める「＋5」の割合を見てください。

5 はずっと 5 のままなのに、3n² のほうは n が10倍になるたびに100倍になります。あっという間に、全体がほぼ 3n² だけで決まるようになります。

② 掛けている 3 は、伸び方そのものを変えない

n を10倍にしたとき、3n² が何倍になるかを考えます。3 × (10n)² ＝ 300n² なので、100倍です。

この「100倍」は、係数が 3 でも 100 でも変わりません。係数はグラフの高さを上下させるだけで、傾き（＝伸び方）には触らないのです。

そもそも係数は、どのパソコンで動かすかでも変わる値です。速いパソコンなら小さくなります。計算量は、使ったパソコンの性能に左右されない部分だけを比べるためのものなので、ここは無視します。

残るのは n²。これが O(n²) の中身です。

この表のうち O(log n) と O(n log n) の2つは、log の読み方が分からないと意味が分かりません。次の節で補足します。

log n の読み方：2を何乗したら n になるか

log の読み方がすでに分かっている方は、この節は読み飛ばしてください。 「log₂n は、n を1になるまで半分にし続けた回数」「100万件なら20回」の2つを持っていけば、続きは読めます。

難しい計算ではありません。log₂n は「2を何乗したら n になるか」という意味です。2を6乗すると64なので、log₂64 ＝ 6 です。

同じことを逆からたどると、n を1になるまで半分にし続けた回数になります。かけ算で数えても割り算で数えても、答えは同じ6です。

64件なら6回で1件になります。

100万件でも20。半分にしていくだけで、これほど少ない回数で1件まで絞り込めます。ここが O(log n) の強さです。

底が書いていないのはなぜか

log₂n と小さく 2 を書いたのに、O(log n) には 2 がありません。書き忘れではなく、書かなくても意味が変わらないからです。

底が2でも10でも、件数が◯倍になったときに処理時間が何倍になるかは、まったく同じになります。変わるのは目盛りだけで、伸び方は変わりません。O記法はもともと決まった倍率（係数）を書かない約束なので、底も書かない、というわけです。

読むときは、底は2だと思って構いません。 半分にした回数を数えているので2ですし、試験でも具体的な回数を問う問題なら log₂n と底を明記してくれます。

実際の回数を並べてみる

倍率だけでは実感しにくいので、実際に何回ぶんの手間がかかるかを並べます。

読み取ってほしいのは2つです。

① 件数が少ないうちは、差が問題にならない。 1,000件なら、いちばん遅い O(n²) でも100万回です。いまのパソコンなら一瞬で終わります。

② 件数が増えると、手がつけられなくなる。 100万件では O(n²) が1兆回。ここまで来ると、現実的な時間では終わりません。

データが少ないうちは差が出ないのに、増えた途端に破綻する。 これが計算量を気にする理由です。作っているときは動いていたのに、本番で件数が増えたら終わらなくなった、という事故がこうして起こります。

O(n log n)：縦 × 横

いちばん形が読み取りにくいのが O(n log n) です。ここも分解すれば難しくありません。

式をそのまま読むと n × log n。掛け算なので、何と何を掛けているのかが分かればいいことになります。

8件を並べ替えてみます。5 3 8 1 9 2 7 4 を小さい順にします。やり方は、2つずつ組にしてそろえ、その組どうしを合体させていく方法です（マージソート）。

ここで、掛ける2つの数が見えます。

• 段の数は 3。毎回2組ずつ合体するので、段の数は「8を半分にし続けた回数」と同じ。つまり log₂8 ＝ 3 です
• どの段でも、8件すべてに触っている。第1段も第2段も第3段も、並べ直すために全8件を1回ずつ見ています。これが n ＝ 8

掛けて 8 × 3 ＝ 24。これが n log n の正体です。

n は「1段あたりの件数」、log n は「段の数」。 長方形の面積を求めるように、縦と横を掛けているだけです。

O(log n) との関係もはっきりします。 O(log n) は「1件を探す」ので段の数だけ。O(n log n) は「n件を並べ替える」ので、それを全件ぶん行う。ちょうど n 倍の関係です。

（なお n log n は目安であり上限です。実際に8件で数えると17回ほどで、24より少なくなります。合体の途中で片方が先に尽きると、残りは比べずに済むためです。試験では上限の形だけを問われるので、ここは気にしなくて構いません。）

覚えるのはこの並びだけ

試験で問われるのは、ほぼどちらが緩やかかです。

ここでいう緩やかとは、件数が増えたときの、処理時間の伸び方が緩やかという意味です。件数が10倍になっても処理時間がほとんど変わらなければ緩やか、100倍になるなら急。件数が増えても困りにくいほうが緩やか、と言い換えても構いません。

緩やかな順に並べると、こうなります。

O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²)

この並びさえ言えれば、「最も速いものはどれか」「最も遅いものはどれか」という問題はそのまま解けます。

覚え方：n の扱われ方で読み下す

どちらが緩やかか迷ったら、n がどう扱われているかを見てください。n は「何件を見るか」、log n は「それを何回くり返すか」です。

最後の「全件について全件を見る」が O(n²) の正体です。二重のくり返しを書いていれば、たいていこの形になります。

最悪の場合を見る

計算量というときは、ふつういちばん運が悪かったときを指します。

線形探索（端から1件ずつ順に見ていく探し方）なら、探すものが最後にあった場合で n 回。最初に見つかることもありますが、それは運がよかっただけで、当てにはできません。最悪でもこれで済むという保証のほうが、設計では役に立ちます。

試験ではこう出る

科目A（旧・午前）のアルゴリズム分野で出ます。多いのは、いくつかの計算量を並べて最も緩やか（または最も急）なものを選ばせる問題と、特定のアルゴリズムの計算量を答えさせる問題です。二分探索は O(log n)、線形探索は O(n) の2つは、そのまま問われます。応用情報では、件数を具体的に示して処理時間の比を計算させる形も出ます。

O(n²) と O(n log n) の差が実務上いちばん効くので、並べ替えの話とセットで問われがちです。細かい導出まで覚える必要はなく、緩やかな順の並びと、代表例が2つずつ言えれば、科目Aの出題には足ります。

関連する用語

O記法（オーダ記法）

計算量の書き方。O(n) のように、伸び方の形だけを書く

二分探索

半分ずつ絞る探し方。計算量は O(log n) で、件数が増えてもほとんど伸びない

線形探索

端から1件ずつ見る探し方。計算量は O(n) で、件数に比例して伸びる

整列（ソート）

並べ替えのこと。方式によって O(n²) と O(n log n) に分かれる

スタック

後に入れたものから先に取り出すデータ構造

ミニクイズ

この分野をまとめて解く → アルゴリズムとプログラミングのミニテスト（全44問）

最終更新：2026-10-06