期待計算量
英語表記: Expected Complexity
概要
期待計算量（Expected Complexity）は、「アルゴリズムと計算量」の分野における「計算量解析」の中でも、特に「ケース別解析」において、アルゴリズムの現実的な性能を評価するために用いられる、確率論に基づいた指標です。これは、特定のアルゴリズムが処理を完了するまでにかかる時間の平均的な予測値を示すものです。最悪計算量が起こり得る最大のコストを保証するのに対し、期待計算量は、すべての入力パターン、またはアルゴリズムの動作に含まれるランダム性を考慮し、その発生確率を重みとして算出した平均的な効率を評価します。多くの実用的なアルゴリズムの真の効率を把握するために、非常に重要な概念なのですよ。
詳細解説
期待計算量が、計算量解析における「ケース別解析」の枠組みで、なぜ不可欠なのかを深く掘り下げてみましょう。これは、アルゴリズムの性能評価をより現実に即したものにするための、非常に洗練されたアプローチなのです。
私たちは通常、アルゴリズムの性能を評価する際に「最悪計算量」を重視します。これは、入力データがアルゴリズムにとって最も不利な並び方をした場合に、どれほどの時間（計算ステップ数）がかかるかを示すもので、システムの安定性や保証性能を考える上では非常に重要です。しかし、最悪ケースがめったに発生しないアルゴリズムの場合、最悪計算量だけを頼りにそのアルゴリズムの採用を諦めてしまうのは、もったいない判断かもしれません。
ここに期待計算量の出番があります。期待計算量は、最悪ケースの悲観的な評価と、最良ケースの楽観的な評価の中間に位置し、現実的な利用シーンでの「平均的な振る舞い」を定量的に捉えようとします。
期待計算量の動作原理
期待計算量は、確率論の「期待値」の概念に基づいています。期待値とは、ある事象が起こり得るすべての結果について、その結果と、その結果が起こる確率を掛け合わせたものの合計です。
- 入力または動作の確率分布: まず、アルゴリズムに入力されるデータパターン、あるいはアルゴリズム内部のランダムな選択肢について、それぞれの発生確率 $P(I)$ を設定します。
- 計算量の評価: 各入力パターン $I$ またはランダムな選択肢 $R$ に対して、その場合の計算量 $T(I)$ または $T(R)$ を算出します。
- 重み付き平均の算出: すべてのケースについて、「（計算量）×（発生確率）」を合計します。
期待計算量 $E[T]$ は、以下の式で表されます。
$$E[T] = \sum_{I} T(I) \times P(I)$$
この解析手法が特に力を発揮するのは、「ランダム化アルゴリズム」の評価です。ランダム化アルゴリズムは、処理中に意図的に乱数を用いて動作を決定します。これにより、どんなに入力データが悪意を持って設計されていたとしても、アルゴリズム自身のランダム性によって最悪ケースを回避できる確率が高まります。このような場合、入力データそのもののランダム性を仮定した「平均計算量」よりも、アルゴリズム内部の乱数に焦点を当てた「期待計算量」こそが、その真の効率を示す指標となるのです。
「ケース別解析」の視点から見ると、期待計算
