アルゴリズムの確率的分析

アルゴリズムの分析において、確率的アルゴリズム分析は、アルゴリズムまたは計算問題の計算の複雑さを推定するアプローチです。これは、すべての可能な入力の集合の確率分布に関する仮定から始まります。この仮定は、効率的なアルゴリズムを設計したり、既知のアルゴリズムの複雑さを導出したりするために使用されます。このアプローチは確率的アルゴリズムのアプローチと同じではありませんが、2つを組み合わせることができます。

非確率的、より具体的には決定論的アルゴリズムの場合、最も一般的なタイプの複雑さの推定は、平均ケースの複雑さ とほぼ常に起こる複雑さです。平均ケースの複雑さを取得するには、入力分布が与えられた場合、アルゴリズムの予想時間が評価されますが、ほぼ常に起こる複雑さの推定では、アルゴリズムがほぼ確実に保持される特定の複雑さの推定を許容することを評価します。

確率的（ランダム化）アルゴリズムの確率的分析では、入力分布に加えて、ランダム化ステップにおけるすべての可能な選択肢の分布または平均も考慮されます。

• 償却分析
• 平均的なケースの複雑さ
• 最良、最悪、平均のケース
• ランダムな自己還元性
• 延期決定の原則

• Frieze, Alan M.; Reed, Bruce (1998)、「アルゴリズムの確率的分析」、Habib, Michel、McDiarmid, Colin、Ramirez-Alfonsin, Jorge、Reed, Bruce (編)、Probabilistic Methods for Algorithmic Discrete Mathematics、Algorithms and Combinatorics、vol. 16、Springer、pp. 36–92、doi :10.1007/978-3-662-12788-9_2、ISBN 9783662127889
• Hofri, Micha (1987)、「アルゴリズムの確率的分析：コンピュータアルゴリズムの性能評価のための計算手法について」、Springer、doi :10.1007/978-1-4612-4800-2、ISBN 9781461248002
• Frieze, AM (1990)、「グラフ アルゴリズムの確率的分析」、Tinhofer, G.、Mayr, E.、Noltemeier, H.、Syslo, MM (編)、Computational Graph Theory、Computing Supplementa、vol. 7、Springer、pp. 209–233、doi :10.1007/978-3-7091-9076-0_11、ISBN 9783709190760