無作為性の役割
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/08/06 16:16 UTC 版)
「In-placeアルゴリズム」の記事における「無作為性の役割」の解説
乱択アルゴリズムを使うことで必要な領域を劇的に減らすことができる場合が多い。例えば、ある2つのノードがグラフ内の1つの連結成分に含まれるかどうかを判定する問題を考える。この問題には既知の単純で決定的な in-placeアルゴリズムは存在しない。しかし、1つのノードを選んで約 20n3回ランダムウォークを行うと、もう1つのノードが同じ連結成分に含まれていることを発見する確率が非常に高い。また、素数判定にも確率的(乱択) in-placeアルゴリズムが存在するし(ミラー-ラビン素数判定法など)、素因数分解にも同様のアルゴリズムが存在する(ポラード・ロー素因数分解法)。
※この「無作為性の役割」の解説は、「In-placeアルゴリズム」の解説の一部です。
「無作為性の役割」を含む「In-placeアルゴリズム」の記事については、「In-placeアルゴリズム」の概要を参照ください。
- 無作為性の役割のページへのリンク