ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

計算量を数える

回 1-3　道 1 数と論理と計算量

計算量は、データの数 n が増えたときに、手順の回数がどう増えるかの見積もりです。1 重のループは n 回、2 重のループは n × n 回回り、n = 1000 なら 1000 回と 1000000 回です。O 記法 (Big-O) は、一番速く伸びる項だけを残して係数を落とし、O(n) や O(n²) のように書きます。

目安 50 分1-3 (1-1〜1-8 の中)

読み終えたら入れ子のループの回数を、n の式で書ける

この頁の流れ

  1. 1データが増えると、時間は何倍になるのか
  2. 2計算量はどう数えるのか
  3. 3動かして確かめる
  4. 4計算量の見積もりはどこで外れるのか
  5. 5計算量は仕事でどう確かめるのか
  6. 6関わる実例
  7. 7よくある問い
  8. 8確認クイズ
  9. 9説明課題
  10. 10もっと深く
  11. 11一次資料
  12. 12次へ

ループの形を見て、データが増えたときに回る回数が足し算で増えるのか、掛け算で増えるのかを切り分けます。

文 ゆめさくコード編集部公開 2026年10月26日更新 2026年10月26日出典を確かめた日 2026年10月26日

データが増えると、時間は何倍になるのか

時間が何倍になるかは、ループの形を見れば、動かす前に見積もれます。その見積もりが計算量 (データが増えたときの手間の増え方) です。

名簿から同じ名前の人を探す処理を、テストでは 10 人の名簿で試しました。すぐに終わったので、そのまま本番に出しました。本番の名簿は 1000 人です。この処理は、本番でも同じように終わるでしょうか。

答えは、処理の中のループの形で決まります。名簿を端から 1 回なめるだけなら、回る回数は 10 回から 1000 回に増えます。全員と全員の組を見比べる形なら、100 回から 1000000 回に増えます。同じ「10 人から 1000 人へ」でも、増え方がまるで違います。

この回では、時計を使わずに、ループが回った回数を数えます。

秒数は機械で変わっても手数は変わらないこと、端から探す手数と目次で引く手数を比べた図

計算量はどう数えるのか

計算量は、データの数を n と置き、手順が何回行われるかを n の式で書いて表します。ここで数えるのは、ループの一番内側の行が実行された回数で、この頁ではこれを「回った回数」と呼びます。

なぜ時間ではなく回数を数えるのか

時間は機械で変わりますが、回数は変わらないからです。同じコードでも、機械や、そのときの混み具合で秒数は変わります。

MIT の講義 6.006 の第 1 回の資料も、性能を機械によらない形で表すために、決まった時間で終わる操作の回数を数えるとしています。

ループの形ごとの回った回数

ループの形と、回った回数の式は次の通りです。

ループの形回った回数n = 10n = 1000
1 重 (for i in range(n))n101000
2 重 (内側も range(n))n × n1001000000
三角形 (内側が range(i))n(n − 1) / 245499500
半分にしていく (n = n // 2)log2 n の小数を切り捨てた数39

表の数は、下の「動かして確かめる」のコードの出力そのものです。

2 重のループは、外側の n 回のたびに内側が n 回回るので、n × n です。

三角形のループは、内側が range(i) なので、i が 0 のとき 0 回、1 のとき 1 回と、外側が進むほど内側が長くなります。足すと 0 + 1 + … + (n − 1) で、これは n(n − 1) / 2 です。n × n の約半分です。

半分にしていくループは、n を 2 で割り続けて 1 になるまで回ります。n が 2 倍になっても、割る回数は 1 回増えるだけです。この回数は log2 n (2 を何回掛けると n になるか) の小数を切り捨てた数になります。

ネストしたループ

O 記法は何を残し、何を落とすのか

O 記法 (Big-O、ビッグ オー) は、回った回数の式から、一番速く伸びる項だけを残し、係数 (項に掛かっている数) を落として書く書き方です。MIT 6.006 の資料も、漸近的な書き方では定数の係数と次数の低い項を無視すると書いています。

三角形のループで確かめます。n(n − 1) / 2 を開くと、n² / 2 − n / 2 です。

  1. 一番速く伸びる項は n² / 2 なので、− n / 2 を落とす
  2. 係数の 1 / 2 を落とす
  3. 残った n² を O(n²) と書く

ですから、三角形のループは O(n²) です。回った回数は 2 重のループの約半分ですが、増え方の形は同じです。O が同じとは、回数が同じではなく、増え方の形が同じという意味です。

よく出る 5 つの O

よく出る 5 つの O を、n を変えて並べると次の通りです。O(log n) の列は半分にしていくループが回った回数で、O(n log n) はそれに n を掛けた数です。

On = 10n = 100n = 1000n = 10000
O(1)1111
O(log n)36913
O(n)101001,00010,000
O(n log n)306009,000130,000
O(n²)10010,0001,000,000100,000,000

O(1) は、n が増えても回数が変わりません。n = 10000 のとき、O(log n) は 13 ですが、O(n²) は 100,000,000 に届きます。

O(log n) の代表は、並んだデータから探す二分探索です。真ん中を見て、探す値が無い側の半分を捨てるので、データが 2 倍になっても見る回数は 1 回しか増えません。道 2 の 線形探索と二分探索 で、回数を数えて確かめられます。

O(n log n) の代表は、速いソートです。マージソートは並び方によらず O(n log n) で、クイックソートは平均が O(n log n)、最悪が O(n²) です。バブルソートのような遅いソートは O(n²) です。道 2 の バブルソートと挿入・選択ソート と クイックソートとマージソート で、同じデータの比べた回数を並べています。

計算量の伸び方

図の O(log n) の棒は、log2 n の小数を切り上げて描いています。表は切り捨てなので、棒と表の数がずれることがあります。

動かして確かめる

どの関数も、一番内側の行で c += 1 を行い、その合計を返します。返る値はそのまま「回った回数」です。

1 本目は、1 重、2 重、三角形、半分にしていくの 4 つの形を、n を変えて数えます。

動かす ループの形ごとに回った回数を数える

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

n = 3
 1重  3
 2重  9
 三角 3
 半分 1
n = 10
 1重  10
 2重  100
 三角 45
 半分 3
n = 100
 1重  100
 2重  10000
 三角 4950
 半分 6
n = 1000
 1重  1000
 2重  1000000
 三角 499500
 半分 9

n = 3 の 2 重のループは 9 回で、上の図の 3 × 3 の表が埋まる数と同じです。三角形は n = 10 で 45、n = 1000 で 499500 になり、n(n − 1) / 2 の式と合います。

2 本目は、n を 2 倍にしたときに、回った回数が何倍になるかを出します。半分にしていくループだけは、倍ではなく、何回増えたかを出します。

動かす n を 2 倍にして倍率を見る

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

n = 100 → 200
 1重 100 → 200 2.00倍
 2重 10000 → 40000 4.00倍
 三角 4950 → 19900 4.02倍
 半分 6 → 7 +1回
n = 200 → 400
 1重 200 → 400 2.00倍
 2重 40000 → 160000 4.00倍
 三角 19900 → 79800 4.01倍
 半分 7 → 8 +1回
n = 400 → 800
 1重 400 → 800 2.00倍
 2重 160000 → 640000 4.00倍
 三角 79800 → 319600 4.01倍
 半分 8 → 9 +1回

1 重は 2.00 倍、2 重は 4.00 倍です。三角形は 4.02 倍や 4.01 倍で、ちょうど 4 倍ではありません。落とした − n / 2 の項が少し効いているからです。半分にしていくループは +1 回です。

3 本目は、上の 5 つの O の表を出したコードです。

動かす 5 つの O を並べる

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

n = 10
 O(1)                 1
 O(log n)             3
 O(n)                10
 O(n log n)          30
 O(n²)              100
n = 100
 O(1)                 1
 O(log n)             6
 O(n)               100
 O(n log n)         600
 O(n²)           10,000
n = 1000
 O(1)                 1
 O(log n)             9
 O(n)             1,000
 O(n log n)       9,000
 O(n²)        1,000,000
n = 10000
 O(1)                 1
 O(log n)            13
 O(n)            10,000
 O(n log n)     130,000
 O(n²)      100,000,000

計算量の見積もりはどこで外れるのか

O 記法は増え方の形だけを表すので、係数、小さい n、入力の中身、隠れたループの 4 つで、見積もりと実際がずれます。

O が同じでも、係数で回数が変わる

O(n) どうしでも、1 個のデータにつき 1 回回るのか、100 回回るのかで、回った回数は違います。O 記法は係数を落とすので、この差は O には出ません。

小さい n では O(n²) の方が少ないこともある

1 個につき 100 回回る A (O(n)) と、全部の組を回る B (O(n²)) の、回った回数を比べます。右端は、回った回数が少ない方です (= は同じ)。

動かす 係数の大きい O(n) と O(n²)

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

n=10   A   1,000 B       100 B
n=50   A   5,000 B     2,500 B
n=100  A  10,000 B    10,000 =
n=200  A  20,000 B    40,000 A
n=1000 A 100,000 B 1,000,000 A

n = 10 と n = 50 では、O(n²) の B の方が少なく回ります。n = 100 で同じになり、n = 200 からは A の方が少なくなります。n = 1000 では、A が 100,000 回、B が 1,000,000 回です。

O が小さい方が速いのは、n が十分に大きいときの話です。データが少ないと決まっている所では、単純なやり方の方が速いこともあります。

最悪と平均は違う

同じコードでも、入力の中身で回数が変わります。リストの in は、前から順に 1 つずつ比べて、見つかったら止まります。Python の公式文書は、リストの x in l を O(n) としています。

in と同じ順で比べる関数を自分で書き、比べた回数を数えます。c += 1 は、== で比べる行の直前にあります。

動かす in と同じ順で比べた回数

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

先頭を探す 1
真ん中 501
末尾 1000
無い物 1000
平均 500.5

1000 個のリストで、先頭の物を探すと比べた回数は 1 です。末尾の物は 1000、リストに無い物も 1000 です。無いことを確かめるには、全部と比べるしかないからです。すべての値を 1 回ずつ探したときの平均は 500.5 です。

テストで先頭に近い物ばかり探していると、本番の「無い物を探す」の重さに気づけません。

ループの中に、隠れたループがある

リストの in、文字列の in や index、文字列の + は、1 行に見えても中でデータの長さに比例した仕事をします。ループの中に置くと、見た目は 1 重でも実際は 2 重です。

次のコードは 2 つの例を数えます。uniq は、見た物をリストにためて、新しい物か in と同じ順で確かめます。数えるのは、比べた回数です。build は、文字列に 1 字ずつ + でつなぎます。つなぐたびに新しい文字列を作り、全部の字を写し直すとして、写した字数を数えます。

動かす 隠れたループを数える

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

n = 10
 比べた回数 45
 写した字数 55
n = 100
 比べた回数 4950
 写した字数 5050
n = 1000
 比べた回数 499500
 写した字数 500500

uniq の比べた回数は、n = 10 で 45、n = 100 で 4950、n = 1000 で 499500 です。i 個目のデータはそれまでの i 個と比べるので、三角形のループと同じ数になり、O(n²) です。

build の写した字数は、n = 1000 で 500500 です。Python の公式文書も、つなぐたびに新しい文字列を作るので、ループで文字列をつないでいくと全体の長さに対して 2 乗で増える、と注意しています。

直し方は、隠れたループを外に出すことです。見た物をためるのはリストではなく set にします。公式文書では、set や dict の探す操作は平均で O(1) です。文字列は、部品をリストにためて、最後に 1 回だけつなぎます。

計算量は仕事でどう確かめるのか

仕事では、ループの中を読み、回数の式を書き、n を 2 倍にして倍率を見る、の 3 つで確かめます。

  1. コードを読むときは、ループの中にある in、index、+、sort を探す。1 行でも中でループしているかを確かめる
  2. 回った回数を n の式で書き、O にする。三角形なら n(n − 1) / 2 で、O(n²)
  3. 試験では、n と 2n で回数か時間を出し、倍率を見る。2 倍なら O(n)、4 倍に近いなら O(n²) を疑う

回数を数える試験は、機械の速さで揺れません。上の uniq の形を固める試験は次の通りです。

回数で O の形を固める試験

def test_uniq_grows_like_n2():
    a = uniq(list(range(100)))
    b = uniq(list(range(200)))
    # 2 倍の n で約 4 倍なら n²
    assert 3.9 < b / a < 4.1

set に直したら、倍率が 2 倍に近いことを確かめる試験に置き換えます。時間を計るのはそのあとです。回数で形をつかんでからなら、係数の差か形の差かを切り分けられます。

関わる実例

Cloudflare の正規表現の障害 (2019年7月2日)

Cloudflare は2019年7月2日、WAF (怪しい通信を止める仕組み) の規則を 1 つ足しました。その規則の正規表現 (文字列の形を表す書き方) が大量の後戻りをして、HTTP と HTTPS を受け持つ CPU を使い切りました。公式ブログの事後報告によると、CPU の使用率は 100% 近くまで上がり、利用者には 502 のエラーの頁が出て、サービスは 27 分止まりました。

報告の付録は、問題の核心を .*.*=.* という形に縮めて説明しています。x=x という 3 字に照らすだけで 23 手かかります。末尾に ; を足した .*.*=.*; では、x=x に 90 手、x= の後ろに x を 20 個並べた文字列には 5,353 手かかります。入力が少し長くなるだけで、手数が急に増えます。

崩れた前提は、「1 回の照合は 1 行で軽い」という見方です。照合の中に、入力の長さで回数が大きく増える隠れたループがありました。報告は原因として、使っていた正規表現の道具に計算量の保証が無かったこと、CPU を使いすぎないための守りが数週間前の作り直しで誤って外れていたこと、試験に CPU の使いすぎを見つける方法が無かったことを挙げています。

出典は Details of the Cloudflare outage on July 2, 2019 (Cloudflare 公式ブログ) です。

ハッシュの衝突でサービスを止める攻撃 (2011年12月28日)

2011年12月28日、oCERT は勧告 oCERT-2011-003 を出しました。多くの言語で、ハッシュ表 (dict のように、鍵から値をすぐ引く表) の鍵の散らし方が予測できたため、わざと同じ置き場にぶつかる鍵を大量に送り込めました。勧告によると、POST で送る値の数に十分な上限が無い Web アプリでは、細工した HTTP の要求で CPU を 100% にでき、それが数時間続くこともありました。対象には Java、PHP、Python、Ruby などが並んでいます。

崩れた前提は、「dict を引くのは O(1)」です。Python の公式文書は、dict の O(1) は平均の場合で、ハッシュの衝突がまれだと仮定していると書いています。すべての鍵が同じハッシュになる最悪の場合、O(1) の操作は O(n) になります。O(n) の操作を n 回くり返せば、上の uniq と同じ三角形の形になり、全体は O(n²) です。

勧告は、Python の直した版が、ハッシュを毎回ばらばらにする仕組み (ハッシュのランダム化) を入れ、既定では切ってあり -R で入れる形だったと書いています。

出典は oCERT-2011-003 multiple implementations denial-of-service via hash algorithm collision (oCERT) です。

よくある問い

計算量と時間計算量は同じですか

この頁で扱った計算量は、時間計算量です。時間計算量は手順の回数の増え方を、空間計算量は使うメモリの量の増え方を表します。ただ「計算量」と言うときは、時間計算量を指すことが多いです。

O(n²) のコードは書いてはいけないのですか

書いてかまいません。上の比べでは、n = 10 や n = 50 で O(n²) の方が少なく回りました。問題は、n がどこまで増えるかを考えずに置くことです。

O(log n) の log の底は何ですか

O 記法では底を書きません。底を変えても係数が変わるだけで、O 記法はその係数を落とすからです。

Python の sort の計算量はどれくらいですか

Python の公式文書は、リストの sort を O(n log n) としています。これは最悪の場合で、すでに並んでいる入力や逆順の入力では、比べる回数が O(n) で済むとも書いています。ループの中で毎回 sort すると、O(n log n) を n 回くり返すことになります。

O と Θ と Ω は何が違いますか

O は上からの押さえで、増え方がこれより速くはならないことを表します。Ω (オメガ) は下からの押さえで、これより遅くはならないこと、Θ (シータ) は上と下の両方で、ちょうどこの形で増えることを表します。MIT 6.006 の資料も、O を上の押さえ、Ω を下の押さえ、Θ をぴったりの押さえとして並べています。仕事の会話では、Θ の意味で O と言うことが多いです。

確認クイズ

答えだと思う選択肢を押すと、その場で正誤と理由が開きます。3 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。

1 問目

次のコードで、n = 100 のとき、c += 1 は何回実行されますか。

三角形のループ

c = 0
for i in range(n):
    for j in range(i):
        c += 1

2 問目

回った回数が 100n + n² になる処理を O 記法で書くと、どれになりますか。

3 問目

n 個のデータを 1 重のループで回し、その中で、見た物をためたリストに in で探しています。全体の計算量はどれですか。

説明課題

次の 3 つのループについて、c += 1 が実行される回数を n の式で書き、O 記法でも書いてください。式と O を 3 行で書いたら、下の模範解答を開いて比べてください。

3 つのループ

# 1 つ目
for i in range(n):
    c += 1
# 2 つ目
for i in range(n):
    for j in range(n):
        c += 1
# 3 つ目
for i in range(n):
    for j in range(i):
        c += 1

模範解答

自分の説明を書いてから開いて、比べてください。

この回の先の一歩

件数が増えたときに遅くなる処理を見つけ、直す前に回数で見積もる力は、どの現場でも速さの相談の出発点になります。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。

もっと深く

この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。

一次資料

どれも 2026年10月26日に開いて、題と中身を確かめました。

  • Details of the Cloudflare outage on July 2, 2019 (Cloudflare 公式ブログ、英語)。2019年7月2日に WAF の規則の正規表現が大量の後戻りで CPU を使い切ったこと、CPU が 100% 近く、502 のエラー、27 分止まったこと、.*.*=.* が x=x に 23 手、.*.*=.*; が 90 手と 5,353 手かかること、正規表現の道具に計算量の保証が無かったこと、守りが作り直しで外れていたこと、試験が CPU の使いすぎを見ていなかったこと
  • oCERT-2011-003 multiple implementations denial-of-service via hash algorithm collision (oCERT、英語)。2011年12月28日の勧告、予測できるハッシュの衝突で CPU を 100% にでき数時間続くこと、POST の値の数の上限が無いこと、対象の言語、Python の直した版がランダム化を既定で切り -R で入れる形だったこと
  • Time complexity of operations on built-in types (Python 公式文書、英語)。リストの x in l が O(n)、dict の O(1) は平均でハッシュの衝突がまれな場合に限り、すべての鍵が同じハッシュなら O(n) になること、文字列をループでつなぐと全体の長さに対して 2 乗になること、set の探す操作が平均で O(1)、sort が最悪で O(n log n) で並んだ入力では比べる回数が O(n) のこと。古い住所 https://wiki.python.org/moin/TimeComplexity はこの頁へ移ったと案内しています
  • Introduction to Algorithms 6.006 Lecture 1 notes (MIT OpenCourseWare、英語、2020年春)。性能を機械によらない形で表すために決まった時間の操作の回数を数えること、漸近的な書き方では定数の係数と次数の低い項を無視すること、O を上の押さえ、Ω を下の押さえ、Θ をぴったりの押さえとして並べていること

次へ

前の回 1-2文字コードと文字化けUnicode、UTF-8、Shift_JIS、BOM
次の回 1-4論理と真理値表AND、OR、NOT、ド・モルガン準備中

道 1 数と論理と計算量の回

  1. 1-12 進数と 16 進数桁の重み、変換、表せる範囲頁で読む
  2. 1-2文字コードと文字化けUnicode、UTF-8、Shift_JIS、BOM頁で読む
  3. 1-3計算量を数えるBig-O、ループの回数この回
  4. 1-4論理と真理値表AND、OR、NOT、ド・モルガン準備中
  5. 1-5リトルエンディアンとビッグエンディアンバイトの並び順、ネットワーク、ファイル頁で読む
  6. 1-6Base64 の仕組み64 字の表、= の詰め物、長さ 4/3頁で読む
  7. 1-7情報量とハフマン符号化ビット、確からしさ、圧縮頁で読む
  8. 1-8チューリングマシンと停止問題テープ、状態、計算できない問題頁で読む

道 1 の頁へ戻るほかの道を見る