計算量 - データサイエンス関連+αのメモ

計算量とは、アルゴリズムが問題を解くときに、どれくらいの計算資源を使うかを表す指標

計算量の種類¶

時間と空間¶

時間計算量（time complexity）：処理にどれくらい時間がかかるか
空間計算量（space complexity）：メモリをどれくらい使うか

入力・操作に対するケース分類¶

同じアルゴリズムでも、入力やランダム性・操作の文脈によって計算量は異なる。以下の5つの観点で整理される。

種類	対象	記法の慣習
最良（best-case）	最も有利な入力	$\Omega(\cdot)$
最悪（worst-case）	最も不利な入力	$O(\cdot)$
平均（average-case）	入力の確率分布に対する期待値	$\Theta(\cdot)$
期待（expected）	アルゴリズム内のランダム性に対する期待値	$O(\cdot)$
償却（amortized）	一連の操作全体の平均コスト	$O(\cdot)$

最良計算量（Best-case）¶

最も有利な入力が与えられたときの計算量。

最良計算量は「都合のよい場合」の性能なので、実用上は最悪計算量や平均計算量の方が重視されることが多い。

例：線形探索

最良：先頭要素が目標値 → $O(1)$
最悪：目標値が末尾or存在しない → $O(n)$

def linear_search(lst, target):
    for i, x in enumerate(lst):
        if x == target:
            return i   # 最良は i=0 のとき O(1)
    return -1          # 見つからない場合は O(n)

最悪計算量（Worst-case）¶

最も不利な入力が与えられたときの計算量。 $O$ 記法で上界を表す

アルゴリズム評価で最もよく使われる指標。「どんな入力に対しても必ずこの時間以内に終わる」という保証になる

例：クイックソート

最悪：ピボットが常に最大/最小値（整列済み入力など） → $O(n^2)$
最良・平均： $O(n \log n)$

最悪ケースを避けるためにランダムピボットを使う → 期待計算量 $O(n \log n)$ が保証される

平均計算量（Average-case）¶

入力の確率分布 を仮定したときの、計算量の期待値

入力が一様分布に従うなど、確率モデルの仮定が必要
最悪より楽観的な評価になることが多い
仮定した分布と実際の入力が乖離すると意味を失う

例：クイックソート（ランダム入力）

入力が一様ランダムなら、ピボットが偏らず $O(n \log n)$ になる

例：線形探索（目標値が一様分布で存在する場合）

E[\text{比較回数}] = \frac{1}{n}\sum_{i=1}^{n} i = \frac{n+1}{2} = O(n)

(1)

期待計算量（Expected complexity）¶

アルゴリズム自体のランダム性（乱数使用）に対する計算量の期待値

平均計算量との違い：

	平均計算量	期待計算量
ランダム性の源	入力の分布	アルゴリズムの乱数
入力	確率的に変化する	最悪ケース入力でも成立

期待計算量はどんな入力に対しても期待値として成立するため、より強い保証

例：ランダムピボットのクイックソート

ランダムにピボットを選ぶ → 最悪入力（整列済み）に対しても期待 $O(n \log n)$

例：ハッシュテーブル（チェイン法）

良いハッシュ関数（or ランダムハッシュ）を使えば、探索の期待計算量は $O(1)$

償却計算量（Amortized complexity）¶

一連の操作全体 にかかるコストを操作数で割った、1操作あたりの平均コスト

個々の操作は高くなることがあるが、それが稀であれば全体として安く抑えられる

例：動的配列（Pythonの list）への append

通常： $O(1)$ （末尾に追加するだけ）
容量超過時： $O(n)$ （新しいメモリを確保して全要素コピー）
容量は2倍ずつ増やすため、コピーは $n$ 回の操作で1回しか起きない

\text{合計コスト} = n + \frac{n}{2} + \frac{n}{4} + \cdots \le 2n = O(n)

(2)

\Rightarrow \text{1操作あたりの償却計算量} = O(1)

(3)

例：スタック（push/pop/multipop）

multipop(k) は $O(k)$ だが、pushした要素しかpopできないため、 $n$ 回の操作全体の合計コストは $O(n)$ → 償却 $O(1)$

まとめ：どれを使うか¶

種類	使いどころ
最悪	アルゴリズムの安全な保証を示したいとき（最も一般的）
平均	典型的な入力でのパフォーマンスを示したいとき
期待	ランダム化アルゴリズムの性能を示すとき
償却	一連の操作の実際のスループットを示したいとき
最良	下界の確認・理論的な議論のとき

「 $O(1)$ で速い」という主張が 最悪なのか償却なのか期待なのか を区別することが重要。たとえばPythonの list.append は最悪 $O(n)$ 、償却 $O(1)$ 。