随机算法.pdf

一个随机算法是一种算法，它采用了一定程度的随机性作为其逻辑的一部分。该算法通常使用均匀随机位作为辅助输入来指导自己的行为，超过随机位的所有可能的选择实现了“平均情况下的”良好业绩的希望。从形式上看，该算法的性能将会是一个随机变量，由随机位决定;因此无论是运行时间，或输出（或两者）是随机变量。在常见的实践中，随机化算法是使用近似的伪随机数发生器代替随机比特的真实来源的;这样的实施可以从预期的理论行为偏离。