DO++ : 乱択アルゴリズム

「乱択アルゴリズム」が共立出版から出ているので読んでいます 乱択アルゴリズム(wikipedia)（ランダマイズドアルゴリズムの方が一般的かもしれない）はアルゴリズムの中に（擬似）乱数が含まれており、動作が決定的ではなく、乱数に依存して動きます。 有名な例では、クイックソートのアルゴリズム中にピボットを選択するところがあるのですが、そこを決定的に最初や真ん中の値ではなく、適当に乱数でランダムに選んだ場合がそれに当たります。 クイックソートは最悪計算量が要素数がnの時、O(n^2)かかってしまう問題点がありますが、ランダムにピボットを選んだ場合、かなり高い確率でO(nlogn)で動作することが言えます。もっとはっきりいうと、比較の回数がαnlogn（αは5よりちょっと大きいぐらい）より大きくなる確率は1/(n^2)以下だということが言えます。つまりnが大きい場合は殆ど間違いなくO(nlogn

[mooz]

randomized algorithm. クイックソートでピボットをランダムに選択した場合を例に．

[YTPX]

乱択アルゴリズム(wikipedia)（ランダマイズドアルゴリズムの方が一般的かもしれない）

[hiromark]

乱択アルゴリズムで何がうれしいか。すごくわかりやすい。

[ZAORIKU]

乱数

[otonasi_kaoru]

確率的勾配降下法