確率アルゴリズム
その実行中で乱数(random numbers)を生成できてかつ乱数の出方に 依存して異なる計算を進められるアルゴリズムのこと。
確率アルゴリズムが実行毎に違う解を出したり、 正しくない解を出したりする可能性がある。
しかし、よい確率アルゴリズムは1に近い確率で正しい解を出す。
従来のアルゴリズムで速く解けるか否かまだ分かっていない問題で、 確率アルゴリズムで素早く解けてしまう問題がたくさん知られている。
これらの確率アルゴリズムは大抵シンプルでコーディングしやすい。
一方、確率アルゴリズムの解析には高度な数学の知識が必要である。 Probabilistic analysis of algorithms
Atlantic City algorithm
Monte Carlo algorithm
Las Vegas algorithm
Principle of deferred decision