計算量 (Big O)

Big O 記法とは

Big O 記法は、アルゴリズムの効率を入力サイズ (n) に対する増加率で表す記法である。最悪ケースの計算量を表し、定数係数は無視する。

主要な計算量

記法	名称	例
O(1)	定数時間	ハッシュテーブルの検索
O(log n)	対数時間	二分探索
O(n)	線形時間	配列の走査
O(n log n)	線形対数時間	マージソート
O(n²)	二次時間	バブルソート
O(2ⁿ)	指数時間	全組み合わせの列挙

具体例

// O(1): 定数時間
const map = new Map([['a', 1]]);
map.get('a'); // ハッシュテーブル: 入力サイズに関係なく一定

// O(n): 線形時間
function find(arr: number[], target: number) {
  for (const item of arr) {
    if (item === target) return true; // 最悪 n 回
  }
  return false;
}

// O(log n): 対数時間
function binarySearch(sorted: number[], target: number) {
  let lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// O(n²): 二次時間
function hasDuplicate(arr: number[]) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true;
  return false;
}

n の大きさと実行時間

n	O(log n)	O(n)	O(n log n)	O(n²)
10	3	10	33	100
1,000	10	1,000	10,000	1,000,000
1,000,000	20	1,000,000	20,000,000	10¹²

DynamoDB の計算量

GetItem (主キー) は O(1)、Query (パーティションキー) は O(log n + k)、Scan (全件走査) は O(n) である。Scan はテーブルが大きくなると遅くなるため、Query を使えるようにキー設計する。

空間計算量

O(1) は変数のみ使用、O(n) は入力と同じサイズの配列を作成、O(n²) は 2 次元配列を作成する場合に該当する。

Lambda での実務的な指針

• Lambda のタイムアウト (最大 15 分) 内に完了する計算量か確認
• O(n²) 以上のアルゴリズムは n が大きい場合に問題になる
• DynamoDB の Scan は避け、Query を使う

理論と実装の両面から学ぶなら関連書籍が参考になる。