随机化算法 编辑
随机化算法，是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下，即该算法在运行的过程中的某一步或某几步涉及一个随机决策，或者说其中的一个决策依赖于某种随机事件。
1
相关
米勒-拉宾质数判定法是一种质数判定法则，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授盖瑞·米勒首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的迈克尔·拉宾教授作出修改，提出了不依赖于该假设的随机化算法。
米勒-拉宾质数判定法是一种质数判定法则，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授盖瑞·米勒首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的迈克尔·拉宾教授作出修改，提出了不依赖于该假设的随机化算法。
费马素性检验是一种质数判定法则，利用随机化算法判断一个数是合数还是可能是素数。
费马素性检验是一种质数判定法则，利用随机化算法判断一个数是合数还是可能是素数。
费马素性检验是一种质数判定法则，利用随机化算法判断一个数是合数还是可能是素数。
米勒-拉宾质数判定法是一种质数判定法则，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授盖瑞·米勒首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的迈克尔·拉宾教授作出修改，提出了不依赖于该假设的随机化算法。
水塘抽样是一系列的随机化算法，其目的在于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到内存的情况。最常见例子为Jeffrey Vitter在其论文中所提及的算法R。