Probabilistic analysis of algorithms とは

アルゴリズムの分析において、アルゴリズムの確率的解析は、アルゴリズムまたは計算上の問題の計算上の複雑さを推定する手法である。すべての可能な入力の集合の確率的分布についての仮定から始まる。この仮定は、効率的なアルゴリズムを設計するため、または既知のアルゴリズムの複雑さを導き出すために使用されます。
このアプローチは、確率論的アルゴリズムと同じではありませんが、2つを組み合わせることができます。
確率論的でない、より具体的には、決定論的アルゴリズムの場合、最も一般的なタイプの複雑さ推定値は、平均の場合の複雑さ(予想される時間の複雑さ)とほぼ常に複雑さです。入力分布を仮定すると、平均事例複雑度を得るために、アルゴリズムの予想時間が評価されるが、ほぼ常に複雑さ推定値に対して、アルゴリズムは、ほぼ確実に所与の複雑さ推定値を認めると評価される。
確率的(無作為化)アルゴリズムの確率分析では、入力分布に加えて、無作為化されたステップにおけるすべての可能な選択の分布または平均化も考慮される。