計算量

計算量#

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

計算量の種類#

時間と空間#

時間計算量（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)\]

期待計算量（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)\]

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

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

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

集計法（aggregate method）：\(n\) 回の操作の合計コストを \(n\) で割る
ポテンシャル法（potential method）：データ構造の「蓄積エネルギー」を定義して各操作のコストを補正する

まとめ：どれを使うか#

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

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

計算量

Contents