確率アルゴリズム

【かくりつあるごりずむ (probabilistic algorithm)】

アルゴリズムの実行中どのような操作を行なうかに関して確率的要素を入れることにより, 平均的な効率を改善できたり, 従来効率の良いアルゴリズムが知られていない問題に対しほとんどの場合効率良く解くことができることがある. そのようなアルゴリズムを確率アルゴリズムという. 乱数を用いることで確率的要素を入れる. 高速だが必ずしも正解を与えるとは限らないものと, 必ず有限時間で正解を与えるが, 非常に時間のかかる例が存在するものとに大別される.