ALGORITHM

計算量（Big O記法）入門
プログラムの速さを見積もる

同じ結果を返すコードでも、データが増えたときの速さには大きな差が出ます。その「増え方」をざっくり表すのが計算量（Big O記法）です。難しい数学抜きで、コードを見て速さを見積もる感覚を身につけましょう。

📅 2026-07-23✍ progo編集部

計算量とは「データが増えたときの伸び方」

計算量は、入力データの件数を n としたとき、処理にかかる手数がどれくらいの勢いで増えるかを表します。実際の秒数ではなく「増え方の傾向」を見るのがポイントです。n が10でも100万でも、傾向が分かれば速さを予測できます。

下にいくほど、データが増えたときに遅くなりやすいと考えてください。

配列の何番目かを直接取り出す処理は、件数がいくつでも1手で終わります。

function first(arr) {
  return arr[0];  // 件数に関係なく一定
}

配列を最初から最後まで1回なめる処理は、件数が2倍になれば手数もおよそ2倍です。

function sum(arr) {
  let total = 0;
  for (const x of arr) total += x;  // n回まわる
  return total;
}

ループの中でさらにループを回すと、件数の二乗で手数が増えます。100件で1万手、1000件で100万手と、一気に重くなります。

// すべてのペアを比較（重い）
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    compare(arr[i], arr[j]);
  }
}

「配列の中で重複を探す」ような処理は、うっかりO(n²)になりがちです。ハッシュ（オブジェクトやSet）を使うとO(n)に改善できることが多いです。

ソート済みデータから目的の値を探す二分探索は、1回の比較で候補を半分に絞ります。100万件でも約20回で見つかります。効率のよさが際立つパターンです。

Big Oでは「増え方の主役」だけを見ます。2n + 3 も n も、大きく見ればどちらもO(n)。細かい係数より、n²なのかnなのかという「桁の違い」に注目します。

まずは「ループが何重か」を数えるだけでも、計算量の当たりがつきます。二重ループを見たら「O(n²)かも、改善できないか？」と考える——この習慣が、遅いコードに気づく第一歩です。実際に配列処理を書いて、progoのブラウザ実行環境で試してみましょう。

▼ ブラウザですぐにコードを試せます（インストール不要）