配列操作の計算量とは何か
「計算量」は、要素数を (n) としたとき操作に必要なステップ数の目安です。ここが重要です：操作ごとに増え方が違います。例えば末尾に追加（push）はほぼ一定時間ですが、先頭に追加（unshift）は要素を全てずらすため時間が線形（要素数に比例）になります。これを知ると、遅い処理を避ける設計が自然に選べます。
基本の性質（ランダムアクセス・走査・長さ）
インデックスアクセスは一定時間
配列の arr[i] 読み取り／書き込みはほぼ (O(1)) です。インデックスが決まっていれば高速にアクセスできます。
全要素を一度見る処理は線形
for／for...of／map／filter／reduce など一周する処理は (O(n))。ここが重要です：1回の走査は妥当ですが、入れ子にすると (O(n^2)) になりやすいので避けます。
length の取得は一定時間
arr.length は (O(1))。長さを参照するだけならコストは無視できます。
よく使う操作の計算量（暗記しておく基本）
末尾操作（速い）
- push（末尾に追加）、pop（末尾から削除）は (O(1))。
arr.push(x); // O(1)
arr.pop(); // O(1)
先頭操作（遅い）
- unshift（先頭に追加）、shift（先頭から削除）は (O(n))。ここが重要です：全要素のインデックスを詰め直す必要があるため、要素数に比例して遅くなります。
arr.unshift(x); // O(n)
arr.shift(); // O(n)
任意位置の挿入・削除
- splice は位置によります。途中なら後ろの要素の詰め直しが必要で (O(n)) です。
arr.splice(i, 1); // 中間削除は O(n)
arr.splice(i, 0, item); // 中間挿入は O(n)
部分コピー・連結
- slice（部分切り出し）、concat（連結）は結果サイズに比例して (O(k))／(O(n+m))。
const sub = arr.slice(10, 20); // O(k)（切り出す長さ）
const all = a.concat(b); // O(n+m)
検索・判定
- find / findIndex / includes / indexOf は最悪 (O(n))。ここが重要です：頻繁検索するなら辞書化（オブジェクト/Map）へ。
arr.find(x => x.id === id); // O(n)
arr.includes(value); // O(n)
変換・展開
- map / filter / reduce は (O(n))。
- flat は出力サイズに比例（全体をなめる）して (O(n))、深さにより定数倍増。
- flatMap は map + flat と同等で (O(n))。
arr.flat(); // O(n)（生成される要素数）
arr.flatMap(fn); // O(n)
並び替え
- sort は平均 (O(n \log n))。非破壊の toSorted も同様の計算量ですが“元配列を壊しません”。ここが重要です：比較関数が重いと実測が悪化します。キーの前計算で軽くしましょう。
arr.sort((a,b)=>a-b); // 破壊的 O(n log n)
const s = arr.toSorted(...); // 非破壊 O(n log n)
反転
- reverse は (O(n))、非破壊の toReversed も (O(n))。
arr.reverse(); // 破壊的 O(n)
arr.toReversed(); // 非破壊 O(n)
典型的な落とし穴（ここが重要）
先頭操作の乱用で遅くなる
「キュー」を shift/unshift で実装すると (O(n)) が積み重なります。解決策は“末尾中心”に設計することです。
// 末尾キュー（push + shift を避け、ポインタで管理）
let head = 0;
const q = [];
q.push(item); // enqueue O(1)
const x = q[head++]; // dequeue O(1) 相当（配列詰め直しがない）
または Deque 的に「末尾追加・末尾削除」を使うと高速です。
二重ループで (O(n^2)) に陥る
重複チェックや関連づけを二重ループで書くとすぐに遅くなります。辞書化（ハッシュ化）に切り替えましょう。
// 遅い：二重ループ O(n^2)
const unique = [];
for (const x of arr) {
if (!unique.some(y => y.id === x.id)) unique.push(x);
}
// 速い：辞書 O(n)
const seen = new Set();
const unique2 = arr.filter(x => !seen.has(x.id) && seen.add(x.id));
sort 比較関数が重い
new Date(a.date) - new Date(b.date) を比較のたびに毎回呼ぶと (O(n \log n)) の定数倍が大きくなります。キー前計算で軽量化します。
const prepared = arr.map(x => ({ x, key: new Date(x.date).getTime() }));
prepared.sort((a,b)=>a.key-b.key);
const sorted = prepared.map(p=>p.x);
設計で計算量を下げる（実務パターン）
検索は辞書化で (O(1)) に
ID 検索が多いなら配列から辞書（オブジェクト/Map）を作り、即時参照にします。
const dict = Object.fromEntries(list.map(x => [String(x.id), x]));
const hit = dict[id]; // O(1)
まとめて作る・まとめて返す
小さな push を何度も行うのではなく、concat や スプレッドで一括生成すると内部再配置が減り実測が安定します。
const out = [...part1, ...part2]; // 一括 O(n+m)
コピーは必要最小限で
毎回 slice／スプレッドで全コピーすると (O(n)) が積み重なります。“変更箇所だけ再構築”を徹底します。
// 部分更新（必要階層のみコピー）
const next = { ...state, prefs: { ...state.prefs, theme: "dark" } };
ストリーム的に処理
巨大配列は“チャンク単位”に処理・集計し、最後に合成。ピークメモリ・再計算を抑えられます。
for (let i = 0; i < arr.length; i += 10000) {
const chunk = arr.slice(i, i + 10000); // O(chunk)
// chunk を処理
}
実例で体感する計算量の差
先頭削除を大量に行うケース
// 悪い例：毎回 shift（O(n)）で累積遅い
while (arr.length) {
arr.shift(); // 全体が詰まり続ける
}
// 良い例：ポインタで消費（O(1) 相当、最後に切り出し）
let head = 0;
while (head < arr.length) {
const x = arr[head++];
}
arr = arr.slice(head); // 一度だけ O(n-head)
多数検索の最適化
const ids = [101, 202, 303];
// 悪い：find を毎回（合計 O(n * k)）
const hits1 = ids.map(id => list.find(x => x.id === id));
// 良い：辞書化して O(k)
const dict = Object.fromEntries(list.map(x => [x.id, x]));
const hits2 = ids.map(id => dict[id]).filter(Boolean);
まとめ
配列操作の計算量を押さえる核心は「先頭操作は (O(n)) で遅い・末尾操作は (O(1)) で速い」「全走査は (O(n))、ソートは (O(n \log n))」です。二重ループを避けて辞書化で (O(1)) 検索へ、比較関数はキー前計算で軽く、コピーは“必要最小限の部分だけ”。この設計指針に沿えば、初心者でも配列処理の速度を直感的に改善でき、規模が大きくなっても安定して動くコードを書けます。
