ビッグO記法の視覚的入門

概要

• 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) の違いを体感し、 適切なアルゴリズム選択・改善 が可能
• 最悪ケースの計算量 を意識しつつ、 現実的なパフォーマンス も考慮した設計が重要