計算量と Big-O 記法
データ量が増えたとき、処理時間が“どれくらいの勢いで”増えるかを表す物差し。アルゴリズムの良し悪しを規模で比べられる。
- 1.Big-O は データ量 n が増えたときの処理時間の“伸び方”を表す物差し（定数や係数は無視）。
- 2.速い順のイメージ：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。
- 3.見るのは基本「最悪計算時間」。n が小さいうちは差が出にくいが、大きくなると桁違いになる。
なぜ秒数で測らない？
実行時間はCPUや言語で変わります。Big-O は 係数や定数を無視 し、「n が2倍になったら時間は何倍になる？」というスケールの仕方だけを見ます。O(2n+100) も O(n) と書くのはこのためです。
主要なオーダー
| 記法 | 呼び方 | 代表例 |
|---|---|---|
| O(1) | 定数時間 | 配列の添字アクセス、ハッシュの参照 |
| O(log n) | 対数時間 | 二分探索、平衡二分木の探索 |
| O(n) | 線形時間 | 配列を1周（線形探索） |
| O(n log n) | 準線形 | 高速なソート（マージ/クイック/ヒープ） |
| O(n²) | 二乗時間 | 二重ループ（バブルソート、総当たり比較） |
| O(2ⁿ) | 指数時間 | 素朴な部分集合の全探索、ナイーブな再帰フィボナッチ |
ざっくり、ループ1段で O(n)、二重ループで O(n²)。半分ずつ絞るなら O(log n)。「データを一巡」か「分割統治」か「総当たり」かで当たりをつけられます。
n が大きいと“桁違い”になる
n=10 なら O(n²)=100、O(n)=10 で大した差ではありません。しかし n=1,000,000 だと、O(n)=百万、O(n²)=一兆。現実的に終わるか終わらないかの差になります。
逆に、扱う件数が常に小さい（数十件など）なら、O(n²) でも一瞬です。“速い”アルゴリズムは実装が複雑になりがち。まず素直に書き、ボトルネックになってから最適化するのが定石。早すぎる最適化は避けます。
最悪・平均・最良
Big-O は通常 最悪計算時間（worst case） を指します。例えば線形探索は、
- 最良: 先頭で見つかる → O(1)
- 最悪: 末尾、または無い → O(n)
設計では「最悪でも耐えられるか」で見るのが基本です。
時間だけでなく空間も
同じ考え方で 空間計算量（使うメモリの増え方）も測ります。時間を速くするためにメモリを多く使う（メモ化・索引）など、時間と空間はトレードオフになることが多いです。
例：線形探索 vs 二分探索
ソート済み配列から目的の値を探す（n=1,000,000）
線形探索 O(n) → 最悪 約1,000,000 回の比較
二分探索 O(log n) → 最悪 約20 回の比較（毎回半分に絞る）
ただし二分探索は 事前にソートが必要（ソート自体は O(n log n)）。「1回しか探さない」なら線形でも十分、「何度も探す」ならソートしてから二分探索、という使用回数を含めた判断が要ります。
プログラミング Article
計算量と Big-O 記法を実務で読む
TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。
解決すること
アルゴリズム
比較で見る軸
難易度: intermediate / カテゴリ: プログラミング / タグ数: 3
導入後に効く点
速い順のイメージ：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。
先に潰すリスク
用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。
- 難易度
- intermediate
- カテゴリ
- プログラミング
- タグ数
- 3
判断チェックリスト
- 自社の用途が「アルゴリズム / 計算量」に近いか確認する。
- 強みである「Big-O は データ量 n が増えたときの処理時間の“伸び方”を表す物差し（定数や係数は無視）。」が本当に評価軸になるか確認する。
- 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
- 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
- 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
- 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。