- 物理機リージョン/AZ
- ハイパーバイザVM exit で捕まえる
- VMゲストOS
- コンテナnamespace / cgroup
- プロセスアプリ / DB今ここ
本コースの1本目で、O記法は「n が増えたときの増え方」を測る道具だと見ました。今回はそれを秒数に換算し、走らせる前に判断する使い方を扱います。
まず結論
計算量の値打ちは、走らせる前に「n がいくつなら何が問題になるか」を桁で言えることにあります。n=100万で二重ループを書いたら待てない、は測らずに分かります。
観測は現在地を、計算量は傾きを教えます。プロファイルは今のワークロードについての一枚の写真で、来月データが10倍になったときのことは何も語りません。
ある関数がCPUを食っていることをプロファイルで突き止めました。この情報だけで「データが10倍になったときに何秒かかるか」は分かるでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
操作回数を秒に換算すると、走らせる前に結論が出る
本コースの1本目「なぜ「増え方」で測るのか — O記法が言っていないこと」で、O記法は n が増えたときの増え方を表すものだと見ました。ここではそれを実際の秒数に換算します。
必要なのは2つの数字だけです。n に対して何回の操作が必要か(計算量から出る)と、1秒あたり何回の操作ができるか(自分の環境で測る)。前者を後者で割れば秒が出ます。精度は1桁しかありませんが、1桁あれば「一瞬」と「1日仕事」は区別できます。
まず前者を表にします。実機の性能ではなく純粋な計算なので、環境に依りません。
n | n | n log2 n | n^21,000 | 1,000 | 9,966 | 1,000,000 (1.0e+06)100,000 | 100,000 | 1,660,964 | 10,000,000,000 (1.0e+10)1,000,000 | 1,000,000 | 19,931,569 | 1,000,000,000,000 (1.0e+12)
読みどころは n log n が n とほとんど変わらないことです。n=100万で n log₂n は約1993万回、n のたかだか19.9倍。同じ n で n² は1兆回、n の100万倍。n² だけが別世界にいます。
この機では1秒あたり何回できたか
次に後者の数字です。検証環境(Docker / python:3.12-alpine / Apple Silicon、2026-09-18)で timeit.repeat(number=1, repeat=5) の中央値を取りました。
(1) 空ループ for _ in range(N): pass→ 1操作あたり 9.5 ns / 1秒あたり約 105,208,847 操作 (10^8 のオーダー)(2) 整数の加算 s += i→ 1操作あたり 20.8 ns / 1秒あたり約 48,034,460 操作 (10^7 のオーダー)(3) list の添字アクセス L[i]→ 1操作あたり 20.0 ns / 1秒あたり約 49,992,189 操作 (10^7 のオーダー)(4) dict の検索 D[i]→ 1操作あたり 26.9 ns / 1秒あたり約 37,238,718 操作 (10^7 のオーダー)
この機・この言語・このときの負荷で、Python の素の操作は1秒あたり 10^7 オーダーでした。 機械・言語・同時の負荷が変われば値も変わります。「コンピュータは1秒に10^7回」ではありません。自分の環境で測り直してください(末尾の「現場で確かめる」に手順があります)。
その上で、この 10^7 を先ほどの表に当てます。
n | O(n) | O(n log n) | O(n^2)1,000 | 一瞬 | 一瞬 | 1e6 回 → 0.1秒100,000 | 0.01秒 | 0.17秒 | 1e10 回 → 約17分1,000,000 | 0.1秒 | 2秒 | 1e12 回 → 約28時間
n=10万で二重ループを書いたら分単位で待つ。 これが走らせる前に分かります。内側で dict を引いたり関数を呼んだりすればもっと遅くなるので、あくまで桁を掴むための計算です。
n=100万のとき、n log₂n と n² は操作回数でどのくらい違いますか。
見積もりは値を当てるためではなく、種類を判別するために使う
ここで正直に書きます。上の概算は、実測からの外挿と4〜5倍ずれました。
同じ環境で O(n²) のコードを n=8000 まで走らせ、そこから n=100万を掛け算で外挿すると 約6.0時間です(n=100万は実行していません。外挿値です)。一方、上の 10^7 回/秒 による概算は 約28時間。4〜5倍の開きがあります。
- ・4〜5倍のずれは、1桁の精度しかない見積もりでは想定内
- ・外挿値は実行していない。掛け算で出した推定
見積もりは「28時間か6時間か」を当てるためのものではありません。「1秒か、それとも1日か」を判別するためのものです。 どちらの数字も「n=100万の n² は待てない」という同じ結論を出しており、それで判断には足ります。
この粗さを承知して使えば、見積もりは「測る対象を絞る」道具になります。「まず測る」の「まず」は、見積もりの前ではなく、作り直しの前です。
実測はどこまで理論どおりだったか — 素直な側とばらついた側
外挿の元になった実測です。同じ環境での単発測定。
## O(n) — 理論では10倍になるはずn= 10,000 0.29 ms 時間比: -n= 100,000 2.54 ms 時間比: 8.85倍n= 1,000,000 19.19 ms 時間比: 7.54倍n=10,000,000 225.34 ms 時間比: 11.74倍## O(n^2) — 理論では100倍になるはずn= 80 0.13 ms 時間比: -n= 800 12.81 ms 時間比: 102.4倍n= 8,000 1383.16 ms 時間比: 108.0倍## 同じ n で並べると(n=8000)O(n) n=8,000: 0.217 msO(n^2) n=8,000: 1376.33 ms → 6,332 倍
O(n²) 側は 102.4倍と 108.0倍。理論値100倍にほぼ一致しました。
O(n) 側は 8.85倍・7.54倍・11.74倍とばらつきました。 これを「測り損ねた」と読むのは誤りです。O記法は n を十分大きくしたときの増え方の話で、定数項や1回きりの測定のゆらぎまでは保証しません。n² のほうがきれいに出たのは、増え方が急で定数項が埋もれたからです。
この検証機で O(n) のコードの n を10倍したところ、時間は 8.85倍・7.54倍・11.74倍とばらつきました。これをどう読むのが妥当ですか。
観測(プロファイル)
どこが遅いかを教えます。重い関数と、それがCPU時間の何割かは読めます。ただしこれは、いまの n で取った一枚の記録です。「n が10倍になったら何倍か」は読めません。読み方は既存コース「システム性能分析のしくみ」の観測編に譲ります。
計算量の見積もり
n が増えたらどうなるかを教えます。二重ループなら O(n²)、n を10倍で約100倍(この検証では 102.4倍・108.0倍)。n=100万で待てるかも桁で読めます。ただし「いまどこが重いか」は読めません。呼ばれていない n² は問題になりません。
プロファイルと計算量の見積もり。どちらも「性能」の話ですが、それぞれが答えられない問いは何でしょうか。両方を並べると何が言えるようになりますか。
「いまの n」と「将来の n」で分けてみてください。写真に写っているものと、写っていないものは何ですか。
この章のまとめ
- 操作回数 ÷ 1秒あたりの処理回数 = 秒。走らせる前に桁が出る。
- n log n は n のたかだか19.9倍(n=100万)。別世界にいるのは n² だけ。 n=100万で1兆回。
- この検証機では Python の素の操作が1秒あたり 10^7 オーダー。この機・この言語・このときの値で、自分の環境では測り直す。
- 概算(約28時間)と外挿(約6.0時間)は4〜5倍ずれた。見積もりは値を当てる道具ではなく、1秒か1日かを判別する道具。どちらの数字も同じ結論を出した。
- O(n²) の10倍比は 102.4倍・108.0倍で理論どおり。O(n) 側は 8.85〜11.74倍とばらついた。 O記法は n が大きいときの話で、小さい n では定数項が効く。
- 観測は現在地を、計算量は傾きを教える。 「まず測る」の「まず」は、見積もりの前ではなく作り直しの前。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
この検証では n=100万の O(n²) について、概算で約28時間、外挿で約6.0時間という2つの見積もりが出ました。4〜5倍ずれています。この見積もりの使い道として正しいのはどれですか。
用語集(3語)
- 桁で見積もる
- 操作回数を1秒あたりの処理回数で割り、1桁の精度で秒・分・時間に換算すること。値を当てるのではなく、待てる範囲かを判別するのが目的。
- 外挿
- 測った範囲の外側を増え方の式で推定すること。本レッスンの n=100万の n² は実行しておらず、n=8000 の実測から掛け算で出した推定値。
- 傾き
- この教材での言い方。n を増やしたとき時間がどう伸びるかの度合い。計算量が教えるのはこちらで、いま何秒かかっているかではない。