データが10倍になると、処理時間は10倍とは限りません。6種類の計算量を実測して、O記法が何を言っているのかを確かめます。
これは【深掘り】の記事です。本線の順路ではありません。 読まなくても先へは進めます。 本線の1万件で100倍になる — 計算量とO記法を測るの回で、O記法の考え方は一度扱いました。この記事は、その「何倍になるか」を6種類ぜんぶ実測して、表の数字で確かめるだけの回です。 コンピュータ科学深掘りシリーズの続きなので、興味が無ければ飛ばして構いません。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell では打ちません。VMの立て方はVMを29台溜めた話 — Ubuntu Serverの立て方にあります。
前提: VMに Node.js が入っていること。
node --versionが返ればOKです。入っていない場合はnode_modulesは消してよい — npmとパッケージ管理の回で入れています。この記事では v20 以降を想定しています。前提2: この記事は JavaScript の文法を説明しません。
forと関数と配列が読めれば足ります。不安があればJavaScriptの基本|変数・型・比較演算子と、”1″と1が等しくなる理由を先に読んでください。記事に出てくる秒数は、私のVM(2コア割り当て・メモリ4GB)での実測値です。 読者の環境では絶対に同じ数字になりません。 見るのは秒数そのものではなく、「nを10倍にしたら何倍になったか」の列です。そこは環境が違ってもほぼ同じ値になります。
自分で作った管理画面が、公開した週に固まりました。
作っていたのは「登録された会員の中から、重複しているメールアドレスを探して一覧に出す」という、それだけの画面です。手元のテストデータは 100件でした。ボタンを押すと一瞬で結果が出ます。何度押しても一瞬です。私はこれを「速い」と判断して、そのまま出しました。
本番のデータは 10万件ありました。
ボタンを押すと、画面が白くなって、そのまま帰ってきませんでした。 ブラウザが「このページは応答していません」と聞いてきます。サーバーのログを見ても、エラーは1行も出ていません。落ちてはいないのです。ただ、終わらない。
このとき私が最初にやったのは、コードを速くしようとすることでした。
letをconstにした- ループの中の変数をループの外に出した
console.logを消した
1つも効きませんでした。 当たり前です。私が直していたのは「1回あたりのコストを1割減らす」話で、起きていた問題はそこではなかったからです。
問題のコードは、こういう形でした。
// 重複しているメールアドレスを探す(当時書いたもの)
const dups = [];
for (const user of users) {
if (dups.includes(user.email)) continue;
// ↓ この1行が、users をもう1周する
const count = users.filter((u) => u.email === user.email).length;
if (count > 1) dups.push(user.email);
}
users を1周する for の中で、users をもう1周する filter を呼んでいます。つまり 10万 × 10万 = 100億回の比較をしていました。100件のときは 100 × 100 = 1万回です。1万回は一瞬で終わります。100億回は終わりません。
データが 1000倍になったとき、仕事の量は 100万倍になっていました。
私がやるべきだったのは、コードを1割速くすることではなく、「データが10倍になったら、時間は何倍になるのか」を先に知っておくことでした。それを表す道具が O記法です。
O記法は、私にとって長いあいだ「たぶん試験に出る記号」でした。O(n log n) と書いてあっても、それが現実の秒数で何を意味するのかが分かっていませんでした。だから覚えられず、覚えても使えませんでした。
なので、この記事では暗記をやめます。 代わりに、
6種類ぜんぶを実際に走らせて、n を10倍にしたときに時間が何倍になったかを、自分の目で表にします。
これをやると、O記法は記号ではなく「何に比例するか」を書いただけのメモになります。
似たタイトルの記事があります。役割が違います。 この記事は6種類を並べて実測するを扱います。1万件で100倍になる — 計算量とO記法を測る はまず1つの処理で「増え方」を体感するを扱います。
対象レベル: 中級〜上級 / 区分: 発展
この記事でわかること
- O記法は「速さ」を表していない。 表しているのは「データが増えたときの増え方」で、秒数のことは一言も言っていないこと
O(2n)やO(3n + 5)と書かないのには理由がある。 定数や小さい項を捨てるのは手抜きではなく、十分大きい n では結果が変わらないからであること- n が小さいうちは、計算量が悪いほうが速いことがある。
n²/100はnより速い区間が実際に存在し、ある n で必ず逆転すること O(2ⁿ)とO(n!)は、実測しようとすると人生が終わる。 この2つだけは机上の計算で十分で、その理由が n=40 と n=12 で体感できること- 日常で「O記法」と言っているものは、たいていΘ(シータ)のこと。 O・Ω・Θ・o・ω の違いと、なぜ現場ではその区別が消えるのか
- 計算量が同じでも速さは違う。 同じ
O(n)でも、メモリを触る順番だけで数倍変わり、だから最後は必ず測らないといけないこと
この記事でやること
- 計測台を自作する。 関数と n を渡すと実行時間を返す小さな道具を書く。1回しか測らない罠と、ウォームアップの罠を避ける
- 6つの伸び方を実測する。 n = 1,000 / 10,000 / 100,000 / 1,000,000 で走らせ、「10倍にしたら何倍か」の列を必ず付けた表を作る
- 定数を無視してよい理由を、交差点の実測で確かめる。
nと100nとn²/100を並べて走らせ、逆転する n の値を自分で見つける - 記号を整理する。 O・Ω・Θ・o・ω を1枚の表にして、最良・平均・最悪の違いをクイックソートで見る
- メモリの増え方も測る。
process.memoryUsage()で、時間とメモリのトレードオフを数字にする - 自分がやらかした
includesを、実測で直す。O(n²)をSetでO(n)に落として、秒数がどう変わるかを見る - 同じ
O(n)で速さが変わることを測る。 順番に触る版と飛び飛びに触る版を比べて、CPUキャッシュの話に触れる
先に知る言葉
基本的な言葉は用語集にもまとめてあります。ここではこの記事を読むのに必要な分だけを先に置きます。
| 言葉 | 1〜2行の意味 |
|---|---|
| 計算量 | データの量が増えたときに、仕事の量がどう増えるかの見積もり。秒数ではない |
| n | データの個数。この記事では「配列の要素数」「会員の人数」のこと |
| O記法(ビッグオー) | 計算量を「何に比例するか」だけ書く書き方。O(n²) は「n の2乗に比例して増える」 |
定数時間 O(1) | データが何件でも時間が変わらない。配列の arr[500] のような添字アクセス |
対数時間 O(log n) | データが2倍になっても仕事が1回だけ増える。毎回半分に絞る探し方(二分探索) |
| 時間計算量 / 空間計算量 | 前者は時間の増え方、後者はメモリの増え方。両方ある |
performance.now() | Node.js とブラウザにある、ミリ秒を小数で返す時計。Date.now() より細かい |
| 中央値 | 数値を並べて真ん中の値。平均と違い、1回だけ極端に遅かった回に引っぱられない |
| JIT | JavaScript を実行しながら機械語に変換していく仕組み。同じコードは2回目以降が速くなる |
| CPUキャッシュ | CPU のすぐ隣にある小さな高速メモリ。近くのデータをまとめて持ってくるので、順番に触ると速い |
① まず、測る道具を作る
O記法の話をする前に、測れるようにします。 ここを飛ばすと、この記事は他人の数字を眺めるだけの記事になります。
作業場所を作ります。VMの中で打ちます。
v20.x のような文字が返れば準備完了です。「node: command not found」が返る場合は Node.js が入っていません。
1回だけ測ると、嘘をつかれる
最初に私が書いた計測コードは、これでした。
const t0 = performance.now();
targetFunction(n);
const t1 = performance.now();
console.log(t1 - t0);
これで何度か走らせて、私は混乱しました。 同じ関数を同じ n で走らせているのに、返る数字が 12.3 → 41.9 → 13.1 → 12.8 のように暴れるのです。
理由は2つありました。
- VMは自分だけのために動いていない。 バックグラウンドで別のプロセスが動けば、その瞬間だけ遅くなります
- JavaScript は最初の1回が遅い。 JIT が「このコードは何度も呼ばれる」と判断して機械語に最適化するまで、遅い経路で動きます
2番が特に厄介です。 最初の1回だけを測ると、測っているのは「アルゴリズムの速さ」ではなく「JITがまだ働いていない状態の速さ」になります。O記法を確かめたいのに、別のものを測ってしまいます。
なので、計測台はこうします。
- 先に捨て走りをする(ウォームアップ)。この結果は使わない
- 本番の計測を数回まわして、中央値を取る
bench.mjs を書く
以下を貼り付けます。
// bench.mjs — 計測台
// fn(n) を「捨て走り → 本番数回」で走らせ、ミリ秒の中央値を返す
export function bench(fn, n, { warmup = 2, runs = 5 } = {}) {
// ① ウォームアップ(JITに最適化させる。結果は捨てる)
for (let i = 0; i < warmup; i++) fn(n);
// ② 本番計測
const samples = [];
for (let i = 0; i < runs; i++) {
const t0 = performance.now();
fn(n);
const t1 = performance.now();
samples.push(t1 - t0);
}
// ③ 中央値(1回だけ遅かった回に引っぱられないため)
samples.sort((a, b) => a - b);
const mid = Math.floor(samples.length / 2);
return samples.length % 2 === 1
? samples[mid]
: (samples[mid - 1] + samples[mid]) / 2;
}
// 表を1行ずつ出す。前の行との比(何倍になったか)も出す
export function table(label, fn, ns, opts) {
console.log(`\n=== ${label} ===`);
console.log('n'.padStart(10), 'ms'.padStart(12), '前の行の何倍'.padStart(14));
let prev = null;
for (const n of ns) {
const ms = bench(fn, n, opts);
const ratio = prev === null ? '-' : (ms / prev).toFixed(1) + '倍';
console.log(
String(n).padStart(10),
ms.toFixed(3).padStart(12),
String(ratio).padStart(14)
);
prev = ms;
}
}
Ctrl+O → Enter → Ctrl+X で保存します。
この道具のポイントは table() の「前の行の何倍」の列です。 ここがこの記事の主役です。秒数は環境で変わりますが、この倍率は変わりません。
ウォームアップは「無かったことにする」処理ではありません。 JITに最適化させたあとの状態で測る、という意思表示です。実際のサーバーでも、起動直後の数リクエストは遅く、しばらく動かすと速くなります。「起動直後が遅い」のは、あなたのコードのせいではないことがあります。
② 6つの伸び方を、実際に走らせる
いよいよ本題です。1つずつ別のファイルに分けます。 1ファイルにまとめると、遅いものが混ざったときに全部が終わらなくなります。
O(1) — 定数時間。1倍のまま
「データが何件あっても、時間が変わらない」やつです。
import { table } from './bench.mjs';
// n件の配列を先に用意しておく(用意する時間は測らない)
const caches = new Map();
function arrOf(n) {
if (!caches.has(n)) caches.set(n, new Array(n).fill(7));
return caches.get(n);
}
// 先に全部作っておく
[1000, 10000, 100000, 1000000].forEach(arrOf);
// 測るのは「真ん中の要素を1回読む」だけ。100万回やって差を見えるようにする
function o1(n) {
const a = arrOf(n);
const i = (n / 2) | 0;
let s = 0;
for (let k = 0; k < 1000000; k++) s += a[i];
return s;
}
table('O(1) 添字アクセス', o1, [1000, 10000, 100000, 1000000]);
私のVMではこう返りました。
=== O(1) 添字アクセス ===
n ms 前の行の何倍
1000 0.812 -
10000 0.809 1.0倍
100000 0.815 1.0倍
1000000 0.811 1.0倍
n を1000倍にしても、1.0倍のままです。 これが O(1) です。
ここで大事なのは、「0.8ミリ秒だから速い」ではないことです。もし1回のアクセスに3秒かかる処理であっても、n によって変わらなければ O(1) です。O記法は速さを表していません。
[スクリーンショット: 01_o1実測.png] VMの中で node t-o1.mjs を実行し、「前の行の何倍」の列がすべて 1.0倍 になっている画面を撮ってください。この列がこの記事の主役なので、ここが写っていることが大事です。
O(log n) — 対数時間。ほぼ増えない
「毎回、候補を半分に捨てる」やつです。代表は二分探索。
import { table } from './bench.mjs';
const caches = new Map();
function sortedOf(n) {
if (!caches.has(n)) {
const a = new Array(n);
for (let i = 0; i < n; i++) a[i] = i * 2; // 昇順に並んでいる
caches.set(n, a);
}
return caches.get(n);
}
[1000, 10000, 100000, 1000000, 10000000].forEach(sortedOf);
function binarySearch(a, target) {
let lo = 0, hi = a.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (a[mid] === target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
function ologn(n) {
const a = sortedOf(n);
let found = 0;
// 差が見えるように10万回探す
for (let k = 0; k < 100000; k++) {
if (binarySearch(a, (k % n) * 2) >= 0) found++;
}
return found;
}
table('O(log n) 二分探索', ologn, [1000, 10000, 100000, 1000000, 10000000]);
=== O(log n) 二分探索 ===
n ms 前の行の何倍
1000 4.121 -
10000 5.480 1.3倍
100000 7.033 1.3倍
1000000 10.884 1.5倍
10000000 15.226 1.4倍
n を10倍にしても、1.3〜1.5倍しか増えません。
ここは電卓で確かめられます。log₂(1000) ≈ 10、log₂(10000) ≈ 13.3、log₂(100000) ≈ 16.6。10倍にすると、ループが 3.3回ぶん増えるだけです。10回が13回になるだけなので、時間もそれくらいしか増えません。
O(log n)の凄さは「1000万件でも15ミリ秒」ではなく、「1000万件を1億件にしても、あと3回ループが増えるだけ」というところです。これが、データベースの索引が「速い」と言われる理由の中身です(索引が「速い」の正体 — データベースを自作するで実際に作っています)。
O(n) — 線形時間。ちょうど10倍
「全部を1回ずつ見る」やつです。
import { table } from './bench.mjs';
const caches = new Map();
function arrOf(n) {
if (!caches.has(n)) {
const a = new Array(n);
for (let i = 0; i < n; i++) a[i] = i % 97;
caches.set(n, a);
}
return caches.get(n);
}
[1000, 10000, 100000, 1000000, 10000000].forEach(arrOf);
function on(n) {
const a = arrOf(n);
let s = 0;
for (let i = 0; i < n; i++) s += a[i]; // 1周するだけ
return s;
}
table('O(n) 1周する', on, [1000, 10000, 100000, 1000000, 10000000]);
=== O(n) 1周する ===
n ms 前の行の何倍
1000 0.001 -
10000 0.009 9.0倍
100000 0.088 9.8倍
1000000 0.891 10.1倍
10000000 9.104 10.2倍
n を10倍にすると、時間もちょうど10倍。 これが O(n) です。ここまで素直に出ると気持ちがいいです。
ただし n=1000 の行(0.001ms)は信用しないでください。 短すぎて、performance.now() の解像度と誤差に埋もれています。計測が短すぎるときは倍率が乱れます。 私は最初これで「9.0倍しかない、O(n)じゃないのか」と悩みました。下の行を見れば10.1倍、10.2倍と綺麗に出ています。
O(n log n) — ソート。十数倍
「並べ替える」やつです。まともなソートはだいたいこれです。
import { table } from './bench.mjs';
function onlogn(n) {
// 毎回同じ並びを作る(作る時間も入るが、n に比例なので倍率は壊れない)
const a = new Array(n);
let x = 123456789;
for (let i = 0; i < n; i++) {
x = (x * 1103515245 + 12345) & 0x7fffffff; // 決まった順で散らす
a[i] = x;
}
a.sort((p, q) => p - q);
return a[0];
}
table('O(n log n) ソート', onlogn, [1000, 10000, 100000, 1000000, 10000000]);
=== O(n log n) ソート ===
n ms 前の行の何倍
1000 0.104 -
10000 1.283 12.3倍
100000 15.640 12.2倍
1000000 196.418 12.6倍
10000000 2384.503 12.1倍
10倍にすると、12倍前後。 O(n) の10倍より少し多く、O(n²) の100倍よりはるかに少ない。この「10倍より少し多い」が O(n log n) の手触りです。
なぜ12倍かというと、n の部分で10倍、log n の部分で log(10n)/log(n) ぶん、つまり n=10万あたりでは 1.2倍くらい増えるからです。10 × 1.2 = 12。 数字が合います。
ここが
O(n log n)の重要なところです。n log nは、現実のデータ量ではO(n)と大差ありません。 「ソートを1回入れると重くなるのでは」と心配するより、その隣に二重ループがないかを心配するべきです。
O(n²) — 二重ループ。10倍で100倍
問題児です。私が本番を固めたやつです。
ここで n を大きくしすぎないでください。 上の表と同じ n=1,000,000 でやると、1兆回のループになります。終わりません。 この節の上限は n = 20,000 にします。それでも1回あたり数秒かかります。
import { table } from './bench.mjs';
const caches = new Map();
function arrOf(n) {
if (!caches.has(n)) {
const a = new Array(n);
for (let i = 0; i < n; i++) a[i] = i % 97;
caches.set(n, a);
}
return caches.get(n);
}
[200, 2000, 20000].forEach(arrOf);
function on2(n) {
const a = arrOf(n);
let s = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) s += a[i] === a[j] ? 1 : 0; // 全部と全部を比べる
}
return s;
}
// ⚠️ 上限は 20000。ここから10倍(20万)にすると約100倍=数百秒かかる
table('O(n^2) 二重ループ', on2, [200, 2000, 20000], { warmup: 1, runs: 3 });
=== O(n^2) 二重ループ ===
n ms 前の行の何倍
200 0.044 -
2000 4.297 97.7倍
20000 432.106 100.6倍
10倍にすると100倍。 表にするとあっけないほど素直です。そして、この素直さが恐ろしい。
この表から上へ計算で伸ばせます。
| n | かかる時間(この表から推定) |
|---|---|
| 20,000 | 0.43秒 |
| 200,000 | 約43秒 |
| 2,000,000 | 約72分 |
| 20,000,000 | 約5日 |
私が本番でやったのは n=100,000 の二重ループでした。この表だと 10秒あたり。実際には比較の中身がもっと重かったので、ブラウザが諦めるまで返ってきませんでした。
これが「テストデータ100件では速かった」の答えです。 n=100 は
0.044msの表よりさらに下、0.01ミリ秒です。一瞬で終わるのは当然でした。 100件でどれだけ試しても、10万件で固まることは分かりません。倍率を見ていないと分かりません。
[スクリーンショット: 02_on2実測.png] node t-on2.mjs を実行し、「前の行の何倍」が 97.7倍 100.6倍 になっている画面を撮ってください。このスクショが、この記事で一番大事な1枚です。
O(2ⁿ) と O(n!) — 測ろうとしてはいけない領域
ここは方針を変えます。表を作りません。 作ろうとした結果を見せます。
// ⚠️ このファイルは「終わらないこと」を見るためのものです。
// 途中で Ctrl+C を押して止めて構いません。
// O(2^n): メモ化しないフィボナッチ
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2); // 呼ぶたびに枝が2本に分かれる
}
// O(n!): 全順列を数える
function permCount(arr) {
if (arr.length <= 1) return 1;
let c = 0;
for (let i = 0; i < arr.length; i++) {
const rest = arr.slice(0, i).concat(arr.slice(i + 1));
c += permCount(rest);
}
return c;
}
console.log('--- O(2^n) fib ---');
for (let n = 25; n <= 45; n += 5) {
const t0 = performance.now();
fib(n);
const ms = performance.now() - t0;
console.log(`fib(${n})`.padEnd(10), ms.toFixed(1).padStart(12), 'ms');
}
console.log('--- O(n!) permutations ---');
for (let n = 8; n <= 13; n++) {
const t0 = performance.now();
permCount(Array.from({ length: n }, (_, i) => i));
const ms = performance.now() - t0;
console.log(`perm(${n})`.padEnd(10), ms.toFixed(1).padStart(12), 'ms');
}
私のVMではこうなりました。
--- O(2^n) fib ---
fib(25) 2.9 ms
fib(30) 31.6 ms
fib(35) 348.1 ms
fib(40) 3908.7 ms
fib(45) 43102.4 ms
--- O(n!) permutations ---
perm(8) 1.2 ms
perm(9) 10.4 ms
perm(10) 104.9 ms
perm(11) 1152.6 ms
perm(12) 13840.2 ms
perm(13) は待ちきれずに Ctrl+C で止めました。
数字を読みます。
| 種類 | n を 1(10倍ではない)増やすと |
|---|---|
O(2ⁿ) | 約2倍 |
O(n!) | n 倍(n=12 → 13 なら13倍) |
この2つでは「10倍にしたら何倍か」を測る意味がありません。 n を 1つ増やすだけで倍になるからです。
fib(45)で 43秒。fib(50)なら約 8分、fib(60)なら約 16時間、fib(80)なら約28年perm(12)で 14秒。perm(15)なら約 9時間、perm(20)なら数万年
だからこの2つだけは、実測しません。机上の計算で十分です。 むしろ実測してはいけません。 「動かしてみて遅かったら直そう」という判断が、この領域では通用しないからです。コードを見て
O(2ⁿ)だと気づいた時点で、書き直しが決まります。
ちなみに、fib はメモ化(一度計算した答えを覚える)すれば O(n) になります。O(2ⁿ) は「その問題が難しい」のではなく「その書き方が同じ計算を何億回もやり直している」だけのことが多いです。⑤で実際にメモ化します。
6つを1枚にまとめる
ここまでの実測を並べます。倍率の列だけ見てください。
| 計算量 | 名前 | 代表例 | n を10倍にすると(実測) |
|---|---|---|---|
O(1) | 定数 | 配列の添字アクセス | 1.0倍(変わらない) |
O(log n) | 対数 | 二分探索 | 1.3〜1.5倍 |
O(n) | 線形 | 1周する | 10倍 |
O(n log n) | 線形対数 | ソート | 12倍前後 |
O(n²) | 多項式 | 二重ループ | 100倍 |
O(2ⁿ) | 指数 | メモ化しない再帰 | n を 1 増やすと2倍(測るのは無理) |
O(n!) | 階乗 | 全順列 | n を 1 増やすと n 倍(測るのは無理) |
これが O記法の全部です。 覚えるものは記号ではなく、右端の列です。
③ なぜ定数を無視するのか
ここが、私がずっと納得できなかった部分です。
教科書には「O(3n + 5) は O(n) と書く」「定数倍は無視する」と書いてあります。私はこれを手抜きだと思っていました。3倍は3倍でしょう。3秒かかるものと1秒で終わるものは、明らかに違います。
この疑問は正しいです。そして、答えは「n が十分大きいときの話をしているから」です。
言葉で読んでも納得できなかったので、実測しました。
n・100n・n²/100 を並べて走らせる
3つの関数を用意します。
f_n: n 回ループする →O(n)f_100n: 100n 回ループする → これもO(n)(定数100は捨てられる)f_n2_100: n²/100 回ループする →O(n²)(1/100 は捨てられる)
O記法の主張はこうです。「f_n と f_100n は同じ仲間で、f_n2_100 は別の(もっと悪い)仲間」。
私の直感はこうでした。「n²/100 のほうが 100n より小さいことがあるはずだ」。
両方が正しいです。 走らせます。
const work = (times) => {
let s = 0;
for (let i = 0; i < times; i++) s += i & 7;
return s;
};
const f_n = (n) => work(n); // O(n)
const f_100n = (n) => work(100 * n); // O(n) でもある
const f_n2_100 = (n) => work((n * n) / 100); // O(n^2)
function ms(fn, n) {
for (let i = 0; i < 2; i++) fn(n); // ウォームアップ
const s = [];
for (let i = 0; i < 5; i++) {
const t0 = performance.now();
fn(n);
s.push(performance.now() - t0);
}
s.sort((a, b) => a - b);
return s[2];
}
console.log('n'.padStart(9), 'n'.padStart(11), '100n'.padStart(11),
'n^2/100'.padStart(11), ' 勝っているのは');
for (const n of [100, 1000, 5000, 8000, 10000, 12000, 20000, 50000, 100000]) {
const a = ms(f_n, n);
const b = ms(f_100n, n);
const c = ms(f_n2_100, n);
const winner = c < b ? 'n^2/100' : '100n';
console.log(
String(n).padStart(9),
a.toFixed(3).padStart(11),
b.toFixed(3).padStart(11),
c.toFixed(3).padStart(11),
' ' + winner
);
}
私のVMの結果です。
n n 100n n^2/100 勝っているのは
100 0.000 0.009 0.000 n^2/100
1000 0.001 0.089 0.009 n^2/100
5000 0.005 0.443 0.223 n^2/100
8000 0.007 0.712 0.571 n^2/100
10000 0.009 0.888 0.891 100n
12000 0.011 1.068 1.283 100n
20000 0.018 1.775 3.561 100n
50000 0.045 4.436 22.284 100n
100000 0.089 8.874 89.121 100n
逆転は n = 10,000 で起きました。
これは計算でも出ます。100n と n²/100 が等しくなるのは、
100n = n² / 100→n = 10000
実測した交差点と、電卓の答えが一致しました。
この表から読むこと
1. n が小さいうちは、計算量が悪いほうが速い。
n=1000 では n²/100(0.009ms)が 100n(0.089ms)の 10倍速い。ここだけ見ていたら「O(n²) のほうが速い」と結論してしまいます。
2. ある n を超えると、必ず逆転する。そして差は開き続ける。
n=100,000 では 100n が 10倍速い。n=1,000,000 なら 100倍。この差は永遠に開きます。 定数をどれだけ小さくしても、追いつかれる n が存在します。それが O の主張です。
3. n と 100n は、O記法では同じ仲間。でも実測では 100倍違う。
表の左2列を見てください。どの n でも100倍違います。 O記法はこの100倍を「見ていない」のです。
ここが一番の誤解ポイントでした。 O記法は「定数は重要でない」と言っているのではありません。「定数は、n が増えたときの増え方に影響しない」と言っているだけです。
100倍の定数差は、現実には超重要です。 ただそれはO記法の担当ではなく、実測(プロファイリング)の担当です。
つまり、道具の使い分けはこうなります。
| 知りたいこと | 使う道具 |
|---|---|
| データが増えたら破綻するか | O記法(コードを読むだけで分かる) |
| いま何秒かかっているか | 実測(performance.now() やプロファイラ) |
| どっちが速いか、この n で | 実測(O記法では答えられない) |
[スクリーンショット: 03_交差点.png] node t-constants.mjs を実行し、「勝っているのは」の列が n^2/100 から 100n に切り替わる行(n=10000 のあたり)が写るように撮ってください。
「十分大きい n」とは、いくつか
ここで正直に書きます。「十分大きい n」の値は、問題ごとに違います。
上の例では 10,000 でした。でも定数が 10n と n²/100 なら、交差点は n=1,000 です。定数が 10000n と n²/100 なら n=1,000,000 です。
なので、実務ではこう判断しています。
- 自分のデータが将来どこまで増えるかを見積もる(会員数? 商品数? 1日のログ行数?)
- その範囲で
O(n²)が耐えられるかを、上の表のように計算する - 耐えられないなら、n が小さいうちでも書き直す
私が固めた画面の場合、会員数は「増える一方」でした。増える一方のものに O(n²) を書いてはいけない、が結論でした。逆に「都道府県47件を突き合わせる」なら、47² = 2209 なので O(n²) で構いません。47は増えません。
④ 記号を整理する — O・Ω・Θ・o・ω
ここまで O しか使いませんでした。実は仲間が5つあります。表1枚で片付けます。
| 記号 | 読み | 意味 | 日常語で言うと |
|---|---|---|---|
O(f) | オー | これ以上は悪くならない(上から抑える) | 「最悪でも f くらい」 |
Ω(f) | オメガ | これより良くはならない(下から抑える) | 「少なくとも f はかかる」 |
Θ(f) | シータ | 上も下も f(O かつ Ω) | 「ちょうど f」 |
o(f) | スモールオー | f より厳密に小さい | 「f には絶対に届かない」 |
ω(f) | スモールオメガ | f より厳密に大きい | 「f を必ず超える」 |
具体例で見ます。「配列を1周して合計を出す」処理は、
Θ(n)— 上も下も n。これが正確な言い方O(n)— 正しいO(n²)— これも正しい。「最悪でも n² より悪くはならない」は真だからΩ(1)— これも正しい。「少なくとも1回は動く」は真だから
O(n²) と書いても嘘ではないのがポイントです。上から抑えているだけなので、ゆるく言う分には間違いになりません。
そして正直な補足です。 現場で「この処理は O(n) です」と言うとき、話し手の頭の中はほぼ Θ(n) です。「上限が n」ではなく「だいたい n に比例する」という意味で使っています。
これは厳密には誤用ですが、通じるのでみんなそう使います。 私も使います。区別が必要になるのは、論文を読むときと、面接で突っ込まれたときだけでした。「日常のO記法はΘのこと」と1度だけ覚えておけば、混乱しません。
最良・平均・最悪 — クイックソートで見る
もう1つ、混ざりやすいものを分けます。「O・Ω・Θ」と「最良・平均・最悪」は、別の話です。
- O・Ω・Θ = 関数の増え方をどう抑えるか(数学の話)
- 最良・平均・最悪 = 入力データがどうなっているか(データの話)
代表例がクイックソートです。実際に見ます。
// 教科書どおりのクイックソート(ピボットは常に先頭)
function quicksort(a, lo = 0, hi = a.length - 1, counter = { n: 0 }) {
if (lo >= hi) return counter;
const pivot = a[lo];
let i = lo + 1, j = hi;
while (i <= j) {
counter.n++;
if (a[i] <= pivot) i++;
else { const t = a[i]; a[i] = a[j]; a[j] = t; j--; }
}
const t = a[lo]; a[lo] = a[j]; a[j] = t;
quicksort(a, lo, j - 1, counter);
quicksort(a, j + 1, hi, counter);
return counter;
}
function run(label, makeArray, n) {
const a = makeArray(n);
const t0 = performance.now();
let cmp = 0;
try {
cmp = quicksort(a).n;
} catch (e) {
console.log(label.padEnd(22), ' ← ' + e.constructor.name + '(再帰が深すぎ)');
return;
}
const ms = performance.now() - t0;
console.log(label.padEnd(22), String(cmp).padStart(12), '回',
ms.toFixed(2).padStart(9), 'ms');
}
const n = 20000;
console.log(`n = ${n} / 比較回数と時間`);
// 平均: バラバラ
run('バラバラ(平均)', (n) => {
const a = new Array(n);
let x = 42;
for (let i = 0; i < n; i++) { x = (x * 1103515245 + 12345) & 0x7fffffff; a[i] = x; }
return a;
}, n);
// 最悪: すでに昇順(ピボットが常に最小になる)
run('すでに昇順(最悪)', (n) => Array.from({ length: n }, (_, i) => i), n);
// 最悪: すでに降順
run('すでに降順(最悪)', (n) => Array.from({ length: n }, (_, i) => n - i), n);
n = 20000 / 比較回数と時間
バラバラ(平均) 311472 回 3.94 ms
すでに昇順(最悪) ← RangeError(再帰が深すぎ)
すでに降順(最悪) ← RangeError(再帰が深すぎ)
すでに並んでいるデータを渡したら、クラッシュしました。
理由はこうです。ピボットに常に先頭(=最小値)を選ぶと、分割が「1個」と「残り全部」になります。半分に割れないので、再帰が n段の深さになります。n=20000 では再帰が深すぎてスタックが尽きます。
比較回数も n²/2 = 2億回になり、O(n²) に落ちています。
これがクイックソートの正体です。
| 場合 | いつ起きるか | 計算量 |
|---|---|---|
| 最良 | 毎回ちょうど半分に割れる | Θ(n log n) |
| 平均 | データがバラバラ | Θ(n log n) |
| 最悪 | すでに並んでいる(ピボットの選び方が悪い) | Θ(n²) |
「すでに並んでいるデータ」は、実務で一番よく来ます。 DBから
ORDER BY付きで取ったデータ、日付順のログ、連番のID。私は「ランダムなデータでテストしたから大丈夫」と思っていて、これに気づいていませんでした。実際のライブラリ(
Array.prototype.sortを含む)は、ピボットをランダムか中央値から選ぶ、深くなったら別のソートに切り替える、といった対策が入っています。だから自作しないほうがいい、というのが素直な結論でした。
上の実験で RangeError を見たのは、バグではなく仕様の再現です。壊れたわけではないので、そのまま次へ進んでください。
⑤ 空間計算量 — メモリも増える
ここまで時間だけを見ていました。増えるのは時間だけではありません。
function measure(label, fn, n) {
global.gc && global.gc(); // --expose-gc を付けたときだけ効く
const before = process.memoryUsage().heapUsed;
const t0 = performance.now();
const keep = fn(n); // 返り値を保持しておく(解放されないように)
const ms = performance.now() - t0;
const after = process.memoryUsage().heapUsed;
const mb = (after - before) / 1024 / 1024;
console.log(label.padEnd(26), String(n).padStart(9),
ms.toFixed(2).padStart(9) + ' ms',
mb.toFixed(2).padStart(9) + ' MB');
return keep;
}
// O(1) 空間: 合計だけ持つ
function sumOnly(n) {
let s = 0;
for (let i = 0; i < n; i++) s += i;
return s;
}
// O(n) 空間: 全部を配列に持つ
function buildArray(n) {
const a = new Array(n);
for (let i = 0; i < n; i++) a[i] = i;
return a;
}
const kept = [];
console.log('種類'.padEnd(24), ' n', ' 時間', ' メモリ増');
for (const n of [100000, 1000000, 10000000]) {
kept.push(measure('O(1)空間 合計だけ', sumOnly, n));
}
for (const n of [100000, 1000000, 10000000]) {
kept.push(measure('O(n)空間 配列を作る', buildArray, n));
}
console.log('(保持数:', kept.length, ')');
種類 n 時間 メモリ増
O(1)空間 合計だけ 100000 0.13 ms 0.00 MB
O(1)空間 合計だけ 1000000 1.02 ms 0.00 MB
O(1)空間 合計だけ 10000000 10.31 ms 0.00 MB
O(n)空間 配列を作る 100000 0.72 ms 0.77 MB
O(n)空間 配列を作る 1000000 6.94 ms 7.63 MB
O(n)空間 配列を作る 10000000 78.85 ms 76.29 MB
読めることが2つあります。
O(1)空間はメモリが増えない。 n を100倍にしても 0.00MBO(n)空間は、n に比例して増える。 10倍で 0.77 → 7.63 → 76.29MB。きれいに10倍
1000万件で76MB。1件あたり8バイト(64bit整数1個)です。もしこれがオブジェクトの配列だったら、1件あたり100バイト以上になり、1000万件で1GBを超えます。 私は昔、これで Node.js を heap out of memory で殺しました。そのときのエラーは「メモリが足りません」であって、「あなたの空間計算量が O(n) です」とは言ってくれません。
時間とメモリはトレードオフになる
②で保留した fib を、メモリを使って速くします。
// O(2^n) 時間 / O(n) 空間(再帰の深さ分だけ)
function fibSlow(n) {
if (n < 2) return n;
return fibSlow(n - 1) + fibSlow(n - 2);
}
// O(n) 時間 / O(n) 空間(答えを全部覚える)
function fibMemo(n, memo = new Map()) {
if (n < 2) return n;
if (memo.has(n)) return memo.get(n);
const v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, v);
return v;
}
// O(n) 時間 / O(1) 空間(直前の2つだけ覚える)
function fibLoop(n) {
let a = 0, b = 1;
for (let i = 0; i < n; i++) { const t = a + b; a = b; b = t; }
return a;
}
function one(label, fn, n) {
global.gc && global.gc();
const before = process.memoryUsage().heapUsed;
const t0 = performance.now();
const v = fn(n);
const ms = performance.now() - t0;
const mb = (process.memoryUsage().heapUsed - before) / 1024 / 1024;
console.log(label.padEnd(30), ms.toFixed(2).padStart(11) + ' ms',
mb.toFixed(3).padStart(9) + ' MB');
return v;
}
const n = 35;
console.log(`fib(${n}) を3通りで`);
one('O(2^n)時間 / 素朴な再帰', fibSlow, n);
one('O(n)時間 O(n)空間 / メモ化', fibMemo, n);
one('O(n)時間 O(1)空間 / ループ', fibLoop, n);
fib(35) を3通りで
O(2^n)時間 / 素朴な再帰 351.44 ms 0.001 MB
O(n)時間 O(n)空間 / メモ化 0.09 ms 0.011 MB
O(n)時間 O(1)空間 / ループ 0.00 ms 0.000 MB
メモ化で 351ms → 0.09ms。約4000倍速くなりました。 代わりに 0.011MB のメモリを使っています。
これがトレードオフです。
| 選択 | 時間 | メモリ |
|---|---|---|
| 素朴な再帰 | O(2ⁿ) 最悪 | O(n) |
| メモ化 | O(n) | O(n) メモリを払う |
| ループ | O(n) | O(1) どちらも良い |
ここで見落としがちなこと。 「メモ化すれば速くなる」は正しいですが、この例ではループが一番優れています。 メモ化は「同じ引数で何度も呼ばれる」場合に効く道具で、フィボナッチのように順番に計算できるものは、そもそも表を持つ必要がありません。
キャッシュを入れる前に「そのキャッシュは本当に必要か」を疑う、が学びでした。
⑥ 実務での使い方 — ループが二重なら n²、それで9割足りる
理屈はここまでです。実務で使う形に落とします。
私が普段やっているのは、これだけです。
コードを見て、「入力の大きさに比例して回るループ」が何重になっているかを数える。
– 1重 →
O(n)– 2重 →O(n²)– 半分に絞りながら回る →O(log n)– ソートが入っている →O(n log n)
これで9割足りました。 残り1割(O(n log n) の証明とか、償却計算量とか)が必要になったのは、まだ一度もありません。
ただし「二重ループは見えないところにある」
ここが罠です。私が固めたコードには for が1つしか書かれていませんでした。
for (const user of users) {
if (dups.includes(user.email)) continue; // ← 隠れたループ
const count = users.filter((u) => u.email === user.email).length; // ← 隠れたループ
includes と filter は、中で配列を1周しています。 for の中に書けば、それは二重ループです。
「隠れたループ」の代表を表にします。
| 書き方 | 中でやっていること | 計算量 |
|---|---|---|
arr.includes(x) | 先頭から順に探す | O(n) |
arr.indexOf(x) | 同じ | O(n) |
arr.find(...) / filter(...) | 全部見る | O(n) |
arr.unshift(x) | 全要素を1つずつ後ろへずらす | O(n) |
arr.push(x) | 末尾に足すだけ | O(1)(ならし) |
set.has(x) / map.get(k) | ハッシュで一発 | O(1)(平均) |
obj[key] | 同じ | O(1)(平均) |
arr.sort(...) | 並べ替え | O(n log n) |
includes が O(n)、Set.has が O(1)。 ここが分かれ目です。
unshift が O(n) なのも見落としやすいところです。配列の先頭に足すのは、末尾に足すのとまったく違うコストがかかります。理由は配列は先頭への挿入が遅い — データ構造を自作するで中を開けて確かめています。
実際に直して、実測する
自分がやらかしたコードを、そのまま直します。
function makeUsers(n) {
const us = new Array(n);
for (let i = 0; i < n; i++) {
// 偶数番と次の奇数番が同じメールにする(全員が誰かと重複する)
const id = i % 2 === 0 ? i : i - 1;
us[i] = { id: i, email: `user${id}@example.test` };
}
return us;
}
// ❌ 当時のコード: O(n^2)
function dupsBad(users) {
const dups = [];
for (const user of users) {
if (dups.includes(user.email)) continue;
const count = users.filter((u) => u.email === user.email).length;
if (count > 1) dups.push(user.email);
}
return dups;
}
// ✅ 直したコード: O(n)
function dupsGood(users) {
const seen = new Set();
const dups = new Set();
for (const user of users) {
if (seen.has(user.email)) dups.add(user.email);
else seen.add(user.email);
}
return [...dups];
}
function ms(fn, users) {
const t0 = performance.now();
const r = fn(users);
return { ms: performance.now() - t0, count: r.length };
}
console.log(' n', ' ❌O(n^2)', ' ✅O(n)', ' 何倍速い');
for (const n of [1000, 5000, 20000, 100000]) {
const users = makeUsers(n);
const bad = n <= 20000 ? ms(dupsBad, users) : null; // ⚠️ 10万件は待てないので飛ばす
const good = ms(dupsGood, users);
console.log(
String(n).padStart(9),
(bad ? bad.ms.toFixed(1) + ' ms' : '(省略)').padStart(14),
(good.ms.toFixed(1) + ' ms').padStart(14),
(bad ? (bad.ms / good.ms).toFixed(0) + '倍' : '-').padStart(13)
);
}
n ❌O(n^2) ✅O(n) 何倍速い
1000 18.4 ms 0.3 ms 61倍
5000 431.2 ms 0.9 ms 479倍
20000 6902.5 ms 2.8 ms 2465倍
100000 (省略) 13.1 ms -
n=20,000 で 6.9秒 → 2.8ミリ秒。2465倍。 そして O(n) 版は n=100,000 でも 13ミリ秒で終わります。
❌O(n²) の n=100,000 を省略したのは、手抜きではなく計算した結果です。20,000で6.9秒なので、10万は約25倍(5²)で 170秒あたり。加えて dups.includes のぶんも増えます。記事のために3分待つ価値がないので、省略しました。 ここも「実測せずに机上で判断してよい」場面です。
直した中身は、たった2つです。
users.filter(...)をSetに置き換えた → 「もう見たか」の判定がO(n)からO(1)へdups.includes(...)をSet.addに置き換えた → 重複を持つ器自体をSetにした
ループの数は変わっていません。 for は1つのままです。中の1行の計算量を変えただけで、2465倍になりました。
「配列の中で
includes/find/filterを呼んだら、そこで1周増える」 これだけ覚えておけば、私が起こした障害は起きませんでした。
[スクリーンショット: 04_setで直す.png] node t-dups.mjs を実行し、「何倍速い」の列に 2465倍 のような数字が出ている画面を撮ってください。
⑦ 一番大事な節 — 計算量が同じでも、速さは違う
ここまでで「計算量を読めば分かる」という話をしてきました。最後に、それを自分で崩します。
同じ O(n) のコードで、速さが数倍違うことがあります。
順番に触る版と、飛び飛びに触る版
やることは同じです。1000万個の要素を全部1回ずつ足す。 触る順番だけを変えます。
const N = 10_000_000;
// 同じ配列を使う(データの内容は完全に同じ)
const data = new Float64Array(N);
for (let i = 0; i < N; i++) data[i] = i % 97;
// 触る順番だけを変える index 配列を用意する
function seqIndex(n) {
const idx = new Int32Array(n);
for (let i = 0; i < n; i++) idx[i] = i; // 0,1,2,3,...
return idx;
}
function strideIndex(n, stride) {
const idx = new Int32Array(n);
let k = 0;
for (let start = 0; start < stride; start++) {
for (let i = start; i < n; i += stride) idx[k++] = i; // 飛び飛び
}
return idx;
}
function shuffledIndex(n) {
const idx = seqIndex(n);
let x = 12345;
for (let i = n - 1; i > 0; i--) {
x = (x * 1103515245 + 12345) & 0x7fffffff;
const j = x % (i + 1);
const t = idx[i]; idx[i] = idx[j]; idx[j] = t;
}
return idx;
}
function sumBy(idx) {
let s = 0;
for (let i = 0; i < idx.length; i++) s += data[idx[i]]; // 触る回数は全部同じ
return s;
}
function run(label, idx) {
sumBy(idx); // ウォームアップ
const s = [];
for (let r = 0; r < 3; r++) {
const t0 = performance.now();
sumBy(idx);
s.push(performance.now() - t0);
}
s.sort((a, b) => a - b);
console.log(label.padEnd(30), s[1].toFixed(1).padStart(10) + ' ms');
return s[1];
}
console.log(`要素数 ${N} を全部1回ずつ足す(どれも O(n))`);
const base = run('① 順番に(0,1,2,3...)', seqIndex(N));
run('② 16個飛ばし', strideIndex(N, 16));
run('③ 1024個飛ばし', strideIndex(N, 1024));
const rnd = run('④ 完全にバラバラ', shuffledIndex(N));
console.log(`\n④ は ① の ${(rnd / base).toFixed(1)} 倍かかった(同じ O(n) なのに)`);
私のVMでの結果です。
要素数 10000000 を全部1回ずつ足す(どれも O(n))
① 順番に(0,1,2,3...) 14.2 ms
② 16個飛ばし 38.5 ms
③ 1024個飛ばし 118.9 ms
④ 完全にバラバラ 186.7 ms
④ は ① の 13.1 倍かかった(同じ O(n) なのに)
触る回数は完全に同じです。1000万回。 それでも 13倍違いました。
なぜこうなるのか — CPUキャッシュ
理由はメモリの取ってき方です。
CPU がメモリから1つの値を読むとき、その1つだけを取ってくるわけではありません。 周辺の 64バイトほどをまとめてキャッシュに載せます(キャッシュライン)。「次に使うのは、たぶん隣だろう」という賭けです。
- 順番に触る場合: 1回メモリから取ってくると、
Float64Arrayなら 64 ÷ 8 = 8個ぶんがキャッシュに載ります。次の7回はメモリを触りません。8回に1回だけメモリへ行く - バラバラに触る場合: 毎回まったく別の場所なので、載せた隣の7個は1つも使われません。1000万回ぜんぶメモリへ行く
メモリはCPUキャッシュの数十倍遅いので、これが13倍の差になります。
これは O記法では表現されません。O記法が数えているのは「何回触るか」で、「1回触るのに何秒かかるか」は定数として捨てられているからです。③で見た「定数はO記法の担当ではない」が、ここで戻ってきます。
だからといって「O記法は役に立たない」わけではありません。 ⑥では 2465倍の差が出ました。⑦の差は 13倍です。
桁が2つ違います。 順番は必ずこうです。
1. まず計算量を直す(
O(n²)→O(n)。数千倍) 2. それでも足りなければ、定数を削る(メモリの触り方、キャッシュ。数倍)逆順にやると、数千倍の改善を残したまま、数倍のために苦労します。 私は
letをconstにしていたとき、まさにこれをやっていました。
だから、最後は必ず測る
この記事の結論です。
| 分かること | 方法 | 分からないこと |
|---|---|---|
| データが増えたときに破綻するか | コードを読む(O記法) | いま何秒か |
| いま何秒かかっているか | 測る(performance.now()) | 10倍になったらどうなるか |
両方必要です。片方では足りません。
- O記法だけ見ていると、⑦の13倍を見逃します。「どちらも
O(n)だから同じ」と判断してしまう - 実測だけ見ていると、①の私になります。「100件で一瞬だから速い」と判断してしまう
そして、順番は「読む → 直す → 測る」です。
測り方そのもの(DBの EXPLAIN、プロファイラ、どこを測るか)は、本線の速くする前に必ず測る — パフォーマンス改善とEXPLAINでやっています。この記事は、その「測る前にコードを読む段」の話でした。
つまずいたところ
1. 最初の1回だけを測って、数字が暴れた
同じコードを同じ n で走らせているのに 12.3 → 41.9 → 13.1 と変わり、「計算が間違っているのか」と30分悩みました。原因はJITと、VM上の他のプロセスです。 ①の bench.mjs のように、捨て走り + 数回の中央値にしたら安定しました。
2. n=1000 の行が「9.0倍」で、O(n)ではないと思った
O(n) を実測したとき、最初の倍率が 9.0倍でした。「10倍にならない、理論が違うのか」と疑いました。原因は、計測時間が短すぎて誤差に埋もれていたことです。0.001ミリ秒の測定に意味はありません。下の行(0.891 → 9.104)を見ると10.2倍で、ちゃんと合っていました。 倍率を見るときは、1ミリ秒を超えている行だけを信じます。
3. O(n²) の実測で n を 100万にして、VMを固めた
上の表と同じ n を並べたくて、t-on2.mjs に 1000000 を入れて走らせました。帰ってきませんでした。 メモリも食い始めて、VM全体が重くなり、Ctrl+C も効きづらくなりました。
1兆回のループです。②の表(n=20,000 で 0.43 秒)から計算すれば、約18分かかると分かる話でした。「表を揃えたい」という気持ちで、計算せずに走らせたのが失敗でした。 手が止まったら Ctrl+C、効かなければ別の端末から pkill -f t-on2 で止められます。O(n²) を測るときは、上限を先に計算してからにします。
4. n²/100 のほうが速い区間を見て、「O記法は間違っている」と結論しかけた
③の表で、n=1000 では O(n²) の関数が O(n) の関数より10倍速い。これを見て「O記法は現実に合っていない」と本気で思いました。
間違っていたのは私の読み方でした。 O記法は「常にこちらが速い」とは一言も言っていません。「n が十分大きければ」という前提が最初から付いています。その「十分大きい」がこの例では 10,000 で、実測した交差点と電卓の答え(100n = n²/100 → n = 10000)が一致しました。
5. クイックソートを自作して、RangeError でクラッシュした
④で、すでに昇順のデータを渡したらスタックが尽きました。「バグを書いた」と思ってコードを何度も読み直しました。 バグではなく、最悪ケースの再現でした。ピボットに先頭を選ぶと、並んでいるデータで分割が偏り、再帰が n段の深さになります。
私が持っていた思い込みは「ランダムなデータでテストすれば十分」でした。 実務で来るデータは、ORDER BY 付きのSQLの結果や、日付順のログや、連番のIDです。「すでに並んでいる」が最悪ケースなのは、かなり具合が悪いと分かりました。
6. --expose-gc を付け忘れて、メモリの数字がマイナスになった
⑤を最初に走らせたとき、heapUsed の差が -2.31MB と出ました。処理をしたのにメモリが減っています。測っている途中でガベージコレクションが走ったからです。node --expose-gc t-space.mjs のように先にGCを呼べる状態で走らせると落ち着きました。
それでもメモリの実測は時間より不安定です。 ⑤で見るのは絶対値ではなく、「10倍にしたら10倍になっているか」だけにしてください。
7. 「メモ化すれば速くなる」で止まって、ループ版を書かなかった
⑤で fib をメモ化して 4000倍速くなり、満足して終わろうとしました。ループ版はもっと速く、しかもメモリを1バイトも使いません。 「キャッシュを足す」は思いつきやすく、「そもそも表が要らない」は気づきにくい。トレードオフの表を書いたとき初めて見えました。
8. O(n) 同士なら速さは同じだと思っていた
⑦の結果が一番意外でした。触る回数が完全に同じで、13倍。 「計算量が同じなら、あとは書き方の好みだ」と思っていたので、これは考えを入れ替える必要がありました。
ただし桁を間違えないことも大事でした。⑥の改善は2465倍、⑦の改善は13倍です。先にやるのは常に⑥のほうです。
後片づけ
この記事で作ったものは、すべて ~/cslab/bigo の中だけです。VMの他の場所は触っていません。
bench.mjs と t-*.mjs が並んでいるはずです。中身を消します。
~/cslab に他の実験が無ければ、こちらも消せます。
途中で走らせたプロセスが残っていないか、念のため見ます。②の t-on2.mjs や t-explode.mjs を Ctrl+C で止め損なっていると、CPUを100%使い続けます。
残っていたら、PID を確認して止めます。
pkill node とだけ打たないでください。 VM上で別の Node.js アプリを動かしている場合、それも一緒に落ちます。 -f 'node t-' のようにこのディレクトリのファイル名で絞るのが安全です。
まとめ — 理解できたこと
- O記法は「速さ」を表していない。 表しているのは「データが増えたときの増え方」だけで、秒数のことは何も言っていない
- 覚えるものは記号ではなく、「n を10倍にしたら何倍か」の1列だけ。
O(1)=1倍、O(log n)=1.4倍、O(n)=10倍、O(n log n)=12倍、O(n²)=100倍。これを実測で確かめたので、もう暗記が要らなくなった O(2ⁿ)とO(n!)は実測できない。 n を 1つ増やすだけで2倍、n倍になる。fib(45)で43秒、perm(12)で14秒。この2つだけは机上の計算で判断してよく、むしろ実測してはいけない- 定数を捨てるのは手抜きではない。
100nとn²/100の交差点は n=10,000 で、実測した逆転位置と電卓の答えが一致した。 n が小さいうちはO(n²)が速いことは実際にあり、それでもある n で必ず逆転して、差は永遠に開く - ただし「定数は重要でない」とは誰も言っていない。
nと100nは O記法では同じ仲間だが、実測ではどの n でも100倍違う。定数はO記法の担当ではなく、実測の担当 - 日常で言う「O記法」は、たいてい Θ のこと。
Oは上から抑えるだけなのでO(n²)と言っても嘘ではない。区別が要るのは論文と面接だけで、「日常のOはΘ」と1回覚えれば混乱しない - O・Ω・Θ と、最良・平均・最悪は別の話。 前者は関数の増え方、後者は入力データの形。クイックソートは平均
Θ(n log n)だが、すでに並んでいるデータでΘ(n²)に落ち、n=20000 では再帰が深すぎてクラッシュした - 「すでに並んでいるデータ」は実務で一番よく来る。
ORDER BYの結果、日付順のログ、連番のID。ランダムなデータでのテストは、最悪ケースを1度も踏まない - 増えるのは時間だけではない。
O(n)空間は n に比例してメモリを食う。1000万件の数値の配列(new Array)で76MB。オブジェクトの配列なら1GBを超え、heap out of memoryで殺される - 時間とメモリはトレードオフになる。
fib(35)は素朴な再帰で351ms、メモ化で0.09ms(4000倍)。ただしループ版はメモリも0で、一番優れていた。 キャッシュを足す前に「そのキャッシュは本当に必要か」を疑う - 実務では「ループが何重か」を数えるだけで9割足りる。 そして隠れたループを見落とさないこと。
includesindexOffindfilterunshiftは中で1周している。forの中に書けば、それは二重ループ - 私の障害は、たった2行を
Setにするだけで直った。forの数は変えていない。中の1行の計算量をO(n)からO(1)に変えただけで2465倍になり、10万件でも13ミリ秒で終わった - 計算量が同じでも速さは違う。 触る回数が完全に同じ1000万回でも、順番に触る版とバラバラに触る版で13倍差が出た。CPUがメモリを「64バイトまとめて」持ってくるからで、これはO記法には現れない
- だから順番は「読む → 直す → 測る」。 まずコードを読んで計算量を直し(数千倍)、それでも足りなければ定数を削る(数倍)。逆順にやると、数千倍を残したまま数倍のために苦労する。 私が
letをconstに書き換えていたのは、これだった
参考リンク
- Big O notation — Wikipedia(英語) — O・Ω・Θ・o・ω の定義そのもの。記号の厳密な意味を確かめたいとき
- Time complexity — Wikipedia(英語) — 各計算量クラスの一覧と代表的なアルゴリズム
- performance.now() — MDN — この記事で使った時計。
Date.now()との違い - Array.prototype.includes() — MDN — 「先頭から順に探す」と明記されている。⑥の根拠
- Set — MDN — 「平均して要素数に対して線形より良い」と書かれている部分を読む
- process.memoryUsage() — Node.js 公式ドキュメント — ⑤で使った
heapUsedの意味 - perf_hooks — Node.js 公式ドキュメント — Node.js 側の計測API。もっと本気で測るときはこちら
- Command-line options — Node.js 公式ドキュメント — ⑤で使った
--expose-gcなどの起動オプション - Computer Science Roadmap — roadmap.sh — この記事がどのあたりの項目にあたるか
次に読む
この記事は 【深掘り】コンピュータ科学 の 4 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | 文字コードとUTF-8 — 化けたのは読み方だけ |
| → 次の記事 | 配列と連結リスト — 先頭への追加が数百倍遅い |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- n を10倍にして実測する
- O / Ω / Θ の使い分け
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント