計算量の考え方 — 「制限時間2秒」で何回ループを回せるか

コーディングテストには「実行時間制限」があります。paizaもAtCoderも、だいたい1〜2秒です。正しい答えを出すコードでも、遅ければTLE（Time Limit Exceeded）で不正解になります。

この章で身につけるのは、コードを書く前に「この解き方で間に合うか」を判断する力です。これがないと、時間をかけて実装した解法が無駄になります。逆にこれがあると、書くべき解法が最初から絞れます。

計算量とBig-O記法 — 30秒で復習

計算量は「入力サイズNが増えたとき、処理回数がどう増えるか」の分類で、**O(記法)**で表します。

理論面の丁寧な説明は『コンピュータサイエンスの基礎』第3章 アルゴリズムと計算量にあります。本章はこれを「テストで使う」ことに集中します。

実戦の核心: 10^8回ルール

見積もりに使う経験則はこれだけです。

1秒間に処理できるのは、単純な演算でおよそ10^8（1億）回。

制限時間2秒なら、余裕を見て10^8回以内に収まる解法を選びます。これを使うと、問題文の制約（Nの最大値）から、許される計算量が逆算できます。

学習者

えっ、これ逆に言うと「N ≤ 10^5 なら2重ループは絶対アウト」って、問題を読んだ瞬間に分かっちゃうってこと？

その通りです。10^5の2乗は10^10、つまり100秒コース。制約は出題者からのヒントなんです。「N ≤ 10^5」と書いてあったら、出題者は「O(N²)では解かせません。O(N log N)以下の解法がありますよ」と言っています。問題文を読んだら、本文より先に制約を見る癖をつけましょう。

実例: 同じ問題を3つの計算量で解く

「配列の中から、合計がXになる2つの要素があるか判定せよ」という定番問題で、計算量の違いを体感します。

解法1: 2重ループ — O(N²)

function hasPairSum(nums: number[], x: number): boolean {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === x) return true;
    }
  }
  return false;
}

素直ですが、N = 10^5 だと約5×10^9回の比較でTLEです。

解法2: ソート + 二分探索 — O(N log N)

各要素 a について「x - a が存在するか」を二分探索で調べます。探索1回がO(log N)、それをN回なのでO(N log N)。N = 10^5 なら約1.7×10^6回、余裕で間に合います。

解法3: ハッシュセット — O(N)

function hasPairSum(nums: number[], x: number): boolean {
  const seen = new Set<number>();
  for (const a of nums) {
    if (seen.has(x - a)) return true;  // 探索はO(1)
    seen.add(a);
  }
  return false;
}

「見たことのある値」をSetに入れながら1周するだけ。同じ問題でも、データの持ち方を変えるだけで10^10回が10^5回になる——これが本書全体を貫くテーマです。

計算量を落とす3つの定番ルート

解法2・3で使った「削り方」は、実は数パターンしかありません。本書で繰り返し登場する3ルートを予告しておきます。

「2重ループを書きたくなったら、この3つのどれかで消せないか考える」——それだけで解ける問題が一気に増えます。

見落としがちな計算量の罠

TypeScriptでコーディングテストを受けるとき特有の注意点があります。**一見O(1)に見えて実はO(N)**な操作です。

arr.includes(v)     // O(N)！ Setのhas()ならO(1)
arr.indexOf(v)      // O(N)！
arr.shift()         // O(N)！ 先頭削除は全要素がずれる
str + appendText    // ループ内での文字列連結は要注意（配列にpushしてjoinが安全）

ループの中でこれらを呼ぶと、気づかぬうちにO(N²)になります。「ループ内で配列を線形に触っていないか」はTLEの定番チェックポイントです。

メンター

提出前のセルフチェックは2つだけ。「制約のNは最大いくつか」「自分のコードは何乗のループか」。この掛け算が10^8を超えていたら、書き直しです。慣れれば10秒でできる確認ですよ。

まとめ

• 実行時間制限は1〜2秒。1秒 ≒ 単純演算10^8回が見積もりの基準
• 制約は出題者のヒント。N ≤ 10^5 なら O(N log N) 以下、N ≤ 20 なら O(2^N) もOK——と逆算する
• 計算量を落とす定番ルートは「ハッシュ化」「ソート+二分探索」「累積和・尺取り法」の3つ
• includes / shift などの隠れO(N)操作をループに入れない
• 問題を読む順番は「制約 → 本文」。書く前に計算量、が鉄則

次章からPart 2・データ構造編です。まずは全ての基本、配列と文字列の頻出パターンから始めます。