随机算法的类

Question

从 维基百科 关于随机算法

必须区分 算法 使用随机输入来减少预期的运行时间或内存使用量，但始终在有限的时间内以正确的结果终止，并且 概率算法, 这取决于随机输入，有机会产生不正确的结果（蒙特卡洛算法），或者通过信号失败或未能终止而无法产生结果（拉斯维加斯算法）。

1. 我想知道第一类是如何的算法 使用随机输入来减少预期的运行时间或内存使用量，但始终在有限的时间内以正确的结果终止？
2. IT和拉斯维加斯算法之间可能无法产生结果的差异？
3. 如果我正确理解，那么概率算法和随机算法就不是同一概念。概率算法只是一种随机算法，另一种是使用随机输入来减少预期的运行时间或内存使用情况，但是总是在有界的时间内以正确的结果终止？

Answer 1

1. 此类算法的一个示例是随机快速排序的，您可以随机置入列表或随机选择枢轴值，然后按照迅速的方式使用快速排序。快速排序的运行时间最差为$ O（n^{2}）$，但是在随机列表上的预期运行时间为$ O（n log n）$，因此它始终在$ o之后终止^{2}）$ steps，但是我们可以期望随机实例在$ o（n log n）$ steps之后终止，始终带有正确的答案。

2. 这给出了拉斯维加斯算法的子集。拉斯维加斯算法还允许（低概率）它可能根本无法终止 - 不仅会随着时间的时间终止。

3. 反过来，这些实际上只是一种蒙特卡洛算法，在该算法中，答案可能是不正确的（概率低），至少在概念上与可能没有回答有所不同。

当然，我没有很多细节，您可能想查找正式的这些想法的复杂性ZPP，RP和BPP。

Answer 2

两个术语 随机算法 和 概率算法 在两个不同的情况下使用。 随机算法 是使用随机性的算法，与 确定性算法 那不是。 概率算法, ，例如，用于原始测试的概率算法是使用随机性并可能与某些（希望）小概率造成错误的算法。

必须在 蒙特卡洛算法 和 拉斯维加斯算法. 。拉斯维加斯算法是随机算法，始终返回正确的答案，但它们的运行时间取决于硬币折腾。一个示例是整数分解算法 - 它们始终返回正确的因素，但是它们的运行时间取决于随机性。在说明拉斯维加斯算法的运行时间（例如某种保论算法）时，我们实际上说明了 预期的 运行时间;如果我们不幸，该算法可能会持续更长的时间。

另一方面，蒙特卡洛算法是随机设置的随机算法。这样的算法可能会犯错，但通常错误概率非常低。一个很好的例子是概率原始测试。这些算法非常快，但可能会出错。但是，在实践中，错误概率很慢，它们永远不会犯错。

每种拉斯维加斯算法都可以通过在足够长的时间后停止执行来转换为蒙特卡洛算法，因此在某种意义上，拉斯维加斯算法比蒙特卡洛算法“更好”。