計算量とO記法 — データが10倍で100倍遅くなる

計算量とO記法。量が異なるデータのカードの束とストップウォッチ、ノートパソコン。

データが10倍になると、処理時間は10倍とは限りません。6種類の計算量を実測して、O記法が何を言っているのかを確かめます。

前回: 文字コードとUTF-8 — 化けたのは読み方だけ

これは【深掘り】の記事です。本線の順路ではありません。 読まなくても先へは進めます。 本線の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) でも、メモリを触る順番だけで数倍変わり、だから最後は必ず測らないといけないこと

この記事でやること

  1. 計測台を自作する。 関数と n を渡すと実行時間を返す小さな道具を書く。1回しか測らない罠と、ウォームアップの罠を避ける
  2. 6つの伸び方を実測する。 n = 1,000 / 10,000 / 100,000 / 1,000,000 で走らせ、「10倍にしたら何倍か」の列を必ず付けた表を作る
  3. 定数を無視してよい理由を、交差点の実測で確かめる。 n と 100n と n²/100 を並べて走らせ、逆転する n の値を自分で見つける
  4. 記号を整理する。 O・Ω・Θ・o・ω を1枚の表にして、最良・平均・最悪の違いをクイックソートで見る
  5. メモリの増え方も測る。 process.memoryUsage() で、時間とメモリのトレードオフを数字にする
  6. 自分がやらかした includes を、実測で直す。 O(n²) を Set で O(n) に落として、秒数がどう変わるかを見る
  7. 同じ 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回だけ極端に遅かった回に引っぱられない
JITJavaScript を実行しながら機械語に変換していく仕組み。同じコードは2回目以降が速くなる
CPUキャッシュCPU のすぐ隣にある小さな高速メモリ。近くのデータをまとめて持ってくるので、順番に触ると速い

① まず、測る道具を作る

O記法の話をする前に、測れるようにします。 ここを飛ばすと、この記事は他人の数字を眺めるだけの記事になります。

作業場所を作ります。VMの中で打ちます。

bash
$ mkdir -p ~/cslab/bigo
$ cd ~/cslab/bigo
$ node --version

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つありました。

  1. VMは自分だけのために動いていない。 バックグラウンドで別のプロセスが動けば、その瞬間だけ遅くなります
  2. JavaScript は最初の1回が遅い。 JIT が「このコードは何度も呼ばれる」と判断して機械語に最適化するまで、遅い経路で動きます

2番が特に厄介です。 最初の1回だけを測ると、測っているのは「アルゴリズムの速さ」ではなく「JITがまだ働いていない状態の速さ」になります。O記法を確かめたいのに、別のものを測ってしまいます。

なので、計測台はこうします。

  • 先に捨て走りをする(ウォームアップ)。この結果は使わない
  • 本番の計測を数回まわして、中央値を取る

bench.mjs を書く

bash
$ cd ~/cslab/bigo
$ nano 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倍のまま

「データが何件あっても、時間が変わらない」やつです。

bash
$ nano t-o1.mjs
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]);
bash
$ node t-o1.mjs

私の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) — 対数時間。ほぼ増えない

「毎回、候補を半分に捨てる」やつです。代表は二分探索。

bash
$ nano t-ologn.mjs
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]);
bash
$ node t-ologn.mjs
=== 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回ずつ見る」やつです。

bash
$ nano t-on.mjs
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]);
bash
$ node t-on.mjs
=== 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) — ソート。十数倍

「並べ替える」やつです。まともなソートはだいたいこれです。

bash
$ nano t-onlogn.mjs
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]);
bash
$ node t-onlogn.mjs
=== 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回あたり数秒かかります。

bash
$ nano t-on2.mjs
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 });
bash
$ node t-on2.mjs
=== O(n^2) 二重ループ ===
         n           ms   前の行の何倍
       200        0.044              -
      2000        4.297         97.7倍
     20000      432.106        100.6倍

10倍にすると100倍。 表にするとあっけないほど素直です。そして、この素直さが恐ろしい。

この表から上へ計算で伸ばせます。

nかかる時間(この表から推定)
20,0000.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!) — 測ろうとしてはいけない領域

ここは方針を変えます。表を作りません。 作ろうとした結果を見せます。

bash
$ nano t-explode.mjs
// ⚠️ このファイルは「終わらないこと」を見るためのものです。
//    途中で 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');
}
bash
$ node t-explode.mjs

私の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 より小さいことがあるはずだ」。

両方が正しいです。 走らせます。

bash
$ nano t-constants.mjs
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
  );
}
bash
$ node t-constants.mjs

私の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. 自分のデータが将来どこまで増えるかを見積もる(会員数? 商品数? 1日のログ行数?)
  2. その範囲で O(n²) が耐えられるかを、上の表のように計算する
  3. 耐えられないなら、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・Ω・Θ = 関数の増え方をどう抑えるか(数学の話)
  • 最良・平均・最悪 = 入力データがどうなっているか(データの話)

代表例がクイックソートです。実際に見ます。

bash
$ nano t-quicksort.mjs
// 教科書どおりのクイックソート(ピボットは常に先頭)
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);
bash
$ node t-quicksort.mjs
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 を見たのは、バグではなく仕様の再現です。壊れたわけではないので、そのまま次へ進んでください。


⑤ 空間計算量 — メモリも増える

ここまで時間だけを見ていました。増えるのは時間だけではありません。

bash
$ nano t-space.mjs
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, ')');
bash
$ node --expose-gc t-space.mjs
種類                             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つあります。

  1. O(1) 空間はメモリが増えない。 n を100倍にしても 0.00MB
  2. O(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 を、メモリを使って速くします。

bash
$ nano t-memo.mjs
// 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);
bash
$ node --expose-gc t-memo.mjs
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) なのも見落としやすいところです。配列の先頭に足すのは、末尾に足すのとまったく違うコストがかかります。理由は配列は先頭への挿入が遅い — データ構造を自作するで中を開けて確かめています。

実際に直して、実測する

自分がやらかしたコードを、そのまま直します。

bash
$ nano t-dups.mjs
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)
  );
}
bash
$ node t-dups.mjs
        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つです。

  1. users.filter(...) を Set に置き換えた → 「もう見たか」の判定が O(n) から O(1) へ
  2. 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回ずつ足す。 触る順番だけを変えます。

bash
$ nano t-cache.mjs
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) なのに)`);
bash
$ node t-cache.mjs

私の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の他の場所は触っていません。

bash
$ cd ~/cslab/bigo
$ ls

bench.mjs と t-*.mjs が並んでいるはずです。中身を消します。

bash
$ cd ~
$ rm -rf ~/cslab/bigo
$ ls ~/cslab 2>/dev/null || echo 'cslab は空か、もう無い'

~/cslab に他の実験が無ければ、こちらも消せます。

bash
$ rmdir ~/cslab 2>/dev/null && echo '削除しました' || echo '中身があるので残しました'

途中で走らせたプロセスが残っていないか、念のため見ます。②の t-on2.mjs や t-explode.mjs を Ctrl+C で止め損なっていると、CPUを100%使い続けます。

bash
$ ps aux | grep '[n]ode' || echo 'node のプロセスは残っていません'

残っていたら、PID を確認して止めます。

bash
$ pkill -f 'node t-' && echo '止めました' || echo '対象はありませんでした'

pkill node とだけ打たないでください。 VM上で別の Node.js アプリを動かしている場合、それも一緒に落ちます。 -f 'node t-' のようにこのディレクトリのファイル名で絞るのが安全です。


まとめ — 理解できたこと

  1. O記法は「速さ」を表していない。 表しているのは「データが増えたときの増え方」だけで、秒数のことは何も言っていない
  2. 覚えるものは記号ではなく、「n を10倍にしたら何倍か」の1列だけ。 O(1)=1倍、O(log n)=1.4倍、O(n)=10倍、O(n log n)=12倍、O(n²)=100倍。これを実測で確かめたので、もう暗記が要らなくなった
  3. O(2ⁿ) と O(n!) は実測できない。 n を 1つ増やすだけで2倍、n倍になる。fib(45)で43秒、perm(12)で14秒。この2つだけは机上の計算で判断してよく、むしろ実測してはいけない
  4. 定数を捨てるのは手抜きではない。 100n と n²/100 の交差点は n=10,000 で、実測した逆転位置と電卓の答えが一致した。 n が小さいうちは O(n²) が速いことは実際にあり、それでもある n で必ず逆転して、差は永遠に開く
  5. ただし「定数は重要でない」とは誰も言っていない。 n と 100n は O記法では同じ仲間だが、実測ではどの n でも100倍違う。定数はO記法の担当ではなく、実測の担当
  6. 日常で言う「O記法」は、たいてい Θ のこと。 O は上から抑えるだけなので O(n²) と言っても嘘ではない。区別が要るのは論文と面接だけで、「日常のOはΘ」と1回覚えれば混乱しない
  7. O・Ω・Θ と、最良・平均・最悪は別の話。 前者は関数の増え方、後者は入力データの形。クイックソートは平均 Θ(n log n) だが、すでに並んでいるデータで Θ(n²) に落ち、n=20000 では再帰が深すぎてクラッシュした
  8. 「すでに並んでいるデータ」は実務で一番よく来る。 ORDER BY の結果、日付順のログ、連番のID。ランダムなデータでのテストは、最悪ケースを1度も踏まない
  9. 増えるのは時間だけではない。 O(n) 空間は n に比例してメモリを食う。1000万件の数値の配列(new Array)で76MB。オブジェクトの配列なら1GBを超え、heap out of memory で殺される
  10. 時間とメモリはトレードオフになる。 fib(35) は素朴な再帰で351ms、メモ化で0.09ms(4000倍)。ただしループ版はメモリも0で、一番優れていた。 キャッシュを足す前に「そのキャッシュは本当に必要か」を疑う
  11. 実務では「ループが何重か」を数えるだけで9割足りる。 そして隠れたループを見落とさないこと。includes indexOf find filter unshift は中で1周している。for の中に書けば、それは二重ループ
  12. 私の障害は、たった2行を Set にするだけで直った。 for の数は変えていない。中の1行の計算量を O(n) から O(1) に変えただけで2465倍になり、10万件でも13ミリ秒で終わった
  13. 計算量が同じでも速さは違う。 触る回数が完全に同じ1000万回でも、順番に触る版とバラバラに触る版で13倍差が出た。CPUがメモリを「64バイトまとめて」持ってくるからで、これはO記法には現れない
  14. だから順番は「読む → 直す → 測る」。 まずコードを読んで計算量を直し(数千倍)、それでも足りなければ定数を削る(数倍)。逆順にやると、数千倍を残したまま数倍のために苦労する。 私が let を const に書き換えていたのは、これだった

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 4 / 25 本目です。

記事
← 前の記事文字コードとUTF-8 — 化けたのは読み方だけ
→ 次の記事配列と連結リスト — 先頭への追加が数百倍遅い

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Asymptotic Notation
  • n を10倍にして実測する
  • O / Ω / Θ の使い分け

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次