計算量（computational complexity）

テクノロジ系
アルゴリズムとプログラミング
基本情報
応用情報
重要度 ★★★☆☆

下書き：本文は書き終えていますが、運営者の確認待ちのため未公開です。検索エンジンには noindex を返しています。

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

もう少し詳しい説明

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

ここで大事なのは、「何秒かかるか」ではないということです。同じ処理でも速いパソコンなら短く済みます。機械の性能に左右される秒数を比べても、やり方そのものの善し悪しは分かりません。

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

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

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

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

書き方	件数を100倍にすると	どんな処理か
O(1)	時間は変わらない	件数に関係なく一発で終わる
O(log n)	2倍にもならない	半分ずつ絞り込んでいく
O(n)	100倍	全件を1回ずつ見ている
O(n log n)	約170倍	全件を、何段かくり返して扱う
O(n²)	10,000倍	全件について、また全件を見ている

細かい係数は書きません。「n の2乗に3を掛けて5を足す」という処理でも O(n²) とだけ書きます。件数が大きくなれば、伸び方を決めるのはいちばん強い項だけだからです。

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

log n の読み方：半分にし続けた回数

難しい計算ではありません。log₂n は「n を1になるまで半分にし続けた回数」、それだけです。

64件を、1件になるまで半分にし続けます。下の段が、そこまでに半分にした回数です。最後は6回。この6が log₂64 で、記号の正体はこれだけです。難しい計算ではなく、ただ数えているだけだと考えてください。

64件なら6回なので、log₂64 ＝ 6。逆から見れば「2を6回かけると64」で、どちらから数えても同じです。

件数	半分にした回数＝ log₂n
8	3
1,024	10
1,048,576（約100万）	20

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

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

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

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

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

実際の回数を並べてみる

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

1,000件のときと、100万件のとき。それぞれ何回ぶんの手間がかかるかを並べたものです。倍率ではなく実際の回数なので、そのまま比べられます。件数が増えたときに差が開くのが見て取れます。

読み取ってほしいのは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つずつ組にしてそろえ、その組どうしを合体させていく方法です（マージソート）。

8件を並べ替える様子です。段は3つで、これが log₂8 ＝ 3。そしてどの段でも8件すべてに触っています。8件 × 3段＝ 24 が、n log n の正体です。縦と横を掛けているだけだと考えてください。

ここで、掛ける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より少なくなります。合体の途中で片方が先に尽きると、残りは比べずに済むためです。試験では上限の形だけを問われるので、ここは気にしなくて構いません。）

覚えるのはこの並びだけ

試験で問われるのは、ほぼどちらが緩やかかです。緩やかな順に並べると、こうなります。

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

形	呼び方	代表例
O(1)	定数時間	配列の何番目かを直接取り出す
O(log n)	対数時間	二分探索
O(n)	線形時間	線形探索、合計を出す
O(n log n)	—	速い並べ替え（マージソートなど）
O(n²)	—	遅い並べ替え（バブルソートなど）

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

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

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

形	n の扱われ方	読み下すと
O(1)	n が出てこない	件数に関係なく一定
O(log n)	n が log の中にいる	半分ずつ減らしている
O(n)	n がそのまま	全件を1回ずつ見ている
O(n log n)	n と log n が掛かっている	全件を、段の数だけくり返す
O(n²)	n が掛け合わされている	全件について、また全件を見る

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

最悪の場合を見る

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

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

試験ではこう出る

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

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

ミニクイズ

データ件数を n としたとき、処理時間の増え方が最も緩やかなものはどれか。

正解は 2番：O(log n)

O(log n) は半分ずつ絞り込む形なので、最も緩やかに伸びます。100万件でも20回ほどで済み、二分探索がこれにあたります。O(n) は件数に比例するので100万件なら100万回、O(n log n) はそれをさらに20倍ほどした約2,000万回、O(n²) は100万件なら1兆回相当となり、現実的な時間では終わりません。緩やかな順に並べると O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²) となり、この並びがそのまま出題されます。

間違えた用語の復習リストを見る →

最終更新：2026-09-17