Loading article…
アルゴリズム解析において、確率的アルゴリズム解析は、アルゴリズムまたは計算問題の計算複雑度を推定する手法です。これは、考えられるすべての入力の集合上の確率分布に関する仮定から始まります。この仮定は、効率的なアルゴリズムを設計したり、既知のアルゴリズムの複雑度を導出したりするために用いられます。この手法は確率的アルゴリズムとは異なりますが、両者を組み合わせることも可能です。
非確率的、より具体的には決定論的なアルゴリズムの場合、最も一般的な確率的複雑性推定方法は、平均ケース複雑性とほぼ常に成り立つ複雑性です。平均ケース複雑性を求めるには、入力分布が与えられた場合にアルゴリズムの期待時間を評価します。一方、ほぼ常に成り立つ複雑性推定では、アルゴリズムがほぼ確実に成り立つ 特定の複雑性推定値を持つことを評価します。
確率的（ランダム化）アルゴリズムの確率的解析では、入力分布に加えて、ランダム化されたステップにおけるすべての可能な選択肢の分布または平均も考慮されます。