🎧

ナレーション

再生速度:
「このアルゴリズムは速い」とは何を意味するか。入力が2倍になったとき、実行時間は2倍か、4倍か、それとも爆発的に増えるか。計算量はアルゴリズムの効率を数学的に評価する道具。O(n)、O(n²)、O(log n)。これらの違いを知ることで、適切なアルゴリズムを選べるようになる。

計算量 O記法 時間計算量 空間計算量 NP完全

O記法（ビッグオー記法）

O記法（Big-O Notation）

入力サイズ n に対する計算量の上界を表す。

定数係数と低次の項を無視し、最も支配的な項だけを残す。

例：3n² + 5n + 10 → O(n²)

代表的な計算量

計算量 名前 例 n=1000での目安
O(1) 定数時間 配列アクセス、ハッシュ検索 1
O(log n) 対数時間 二分探索 10
O(n) 線形時間 リスト走査 1,000
O(n log n) 準線形時間 マージソート、クイックソート 10,000
O(n²) 二乗時間 バブルソート、総当たり比較 1,000,000
O(2ⁿ) 指数時間 部分集合の列挙 爆発（不可能）

時間計算量と空間計算量

時間計算量 空間計算量
測定対象 実行に必要な演算回数 実行に必要なメモリ量
トレードオフ しばしば時間と空間はトレードオフ（メモ化など）

計算量クラス

P と NP

P：多項式時間で解ける問題

NP：解の検証が多項式時間でできる問題

NP完全：NPの中で最も難しい問題群

P = NP かどうかは未解決の大問題

NP完全問題の例

巡回セールスマン問題、ナップサック問題、グラフ彩色。これらは効率的な解法が見つかっておらず、近似解法やヒューリスティクスを使う。

実務での応用

WEB開発での応用

データ構造選択：検索が多いならO(1)のハッシュ、順序が必要ならO(log n)のツリー。

ページネーション：全件取得O(n)より、範囲取得O(log n)が効率的。

N+1問題：O(n)のクエリをO(1)にまとめるEager Loading。

キャッシュ：計算結果をメモ化してO(n)→O(1)に。

AI/MLでの応用

Transformerの計算量：自己注意はO(n²)、系列長がボトルネック。

効率的Attention：Linear Attention、Flash AttentionでO(n)に。

近似最近傍探索：厳密なO(n)をANNでO(log n)に。

行列演算：行列積はO(n³)、Strassenで O(n^2.37)。

深掘りリンク