ランダマイゼーション

【らんだまいぜーしょん (randomization)】

ランダマイゼーションは, アルゴリズムの中にランダムな要素を導入し, それにより最悪の場合にとらわれない簡単で実際に速いアルゴリズムを構成しようという手法である. ランダマイゼーションすることによって得られるアルゴリズムをランダム化アルゴリズムと呼ぶ. ランダマイゼーションは, アルゴリズムに対する入力に確率分布を仮定して計算時間を平均的に評価するとかいうのではない. 代表的な手法に, ランダム抽出法, ランダム順添加法などがある.