概要
- Big O記法 は、入力サイズに対するアルゴリズムの性能や成長率を表現する手法
- O(1) （定数時間）、 O(log n) （対数時間）、 O(n) （線形時間）、 O(n^2) （二乗時間）など、代表的な4つのカテゴリを解説
- sum関数 や bubble sort、 binary search などの具体例で理解を深める構成
- 最悪ケース を基準とした計算量評価が基本
- 実践的な改善策 や注意点も紹介
Big O記法の基礎
- Big O記法 は、関数やアルゴリズムの 性能（計算量） を、実際の処理時間ではなく 入力サイズの増加に対する成長率 で表現
- 時間計測ではなく、 入力nが増えたときに処理量がどのように増えるか を分析
- 主に プログラムやアルゴリズムの効率性比較、大規模データへの対応力評価に利用
- O(1) （定数）、 O(log n) （対数）、 O(n) （線形）、 O(n^2) （二乗）など、成長率で分類
- 最悪ケース （worst-case）を基準に評価するのが一般的
線形時間（O(n)）の例：sum関数
sum(n)関数は 1からnまでの合計値をforループ で計算- 入力nが2倍になると、 実行時間もほぼ2倍 となる特徴
- このように 入力サイズに比例して処理回数が増加 するものを O(n) と呼称
- O(n) の「O」は Order（成長の階級） を意味し、 O(n) は「nの階級の成長」を示す
- Big O記法 では 最小の項のみ を記述し、O(2n)やO(n+1)とは書かない
定数時間（O(1)）の例：数式によるsum関数
sum(n)を数式(n*(n+1))/2で計算すると、 入力サイズnに関係なく一定回数の演算 で完了- どんなnでも 処理時間はほぼ変わらない ため、 O(1) （定数時間）と呼ぶ
- O(1) は「瞬時」ではなく「入力サイズに依存しない」ことを意味
- 実際の処理時間が長い場合もあり得る点に注意
二乗時間（O(n^2)）の例：bubble sort
- bubble sort は、隣接要素を比較・交換しながら 複数回ループ して整列
- 最悪ケース（逆順配列）では n回のループをn回繰り返す ため、 O(n^2) （二乗時間）となる
- 入力データの並び順 によって実行回数が変わるが、Big O記法では 最悪ケース を基準
- O(n^2) は大量データに弱いアルゴリズムの典型例
対数時間（O(log n)）の例：binary search
- binary search は、整列済み配列から 中央値で範囲を半分に絞り込む探索法
- 各ステップごとに探索範囲が1/2 になるため、必要なステップ数は log₂n に比例
- 例：1～1,000,000,000の中から1つを当てる場合でも 最大31回の比較 で済む
- O(log n) は大規模データでも極めて効率的なアルゴリズムの代表
実践的なBig O活用例と注意点
リスト内検索
- 配列で値を探す
contains(items, target)は O(n) （線形探索） - 頻繁に検索する場合、 Set構造 を使えば O(1) で高速化可能
- ただし、
new Set(items)の生成自体は O(n) である点に注意
インデックス付きループの罠
- ループ内で
items.indexOf(item)を呼ぶと、 O(n)の探索×n回＝O(n^2) となり非効率 - ループインデックスや
forEach((item, index) => ...)を活用し、 O(n) へ最適化
再帰とキャッシュ
- 再帰的な計算 （例：factorial）は O(n) だが、同じ計算を繰り返す場合は メモ化（キャッシュ） で高速化可能
- 再帰呼び出しの最適化やキャッシュ利用で 計算量の削減 を図る
まとめ
- Big O記法 は、アルゴリズムのスケーラビリティを理解・比較するための 強力な指標
- O(1)、O(log n)、O(n)、O(n^2) の違いを体感し、 適切なアルゴリズム選択・改善 が可能
- 最悪ケースの計算量 を意識しつつ、 現実的なパフォーマンス も考慮した設計が重要