Data Structures Algorithms 简明教程
Randomized Algorithms
随机算法是一种不同的设计方法，该方法是由标准算法采用的，其中少量随机位被添加到其逻辑的部分。它们不同于确定性算法；确定性算法遵循确定的过程以在每次输入通过时获得相同的输出，而随机算法则在每次执行时生成不同的输出。值得注意的是，被随机化的不是输入，而是标准算法的逻辑。
Figure 1: Deterministic Algorithm
与确定性算法不同，随机算法考虑逻辑的随机位与有助于获得输出的输入。
Figure 2: Randomized Algorithm
但是，也不能排除随机算法提供错误输出的可能性。因此，执行称为 amplification 的过程以减少这些错误输出的可能性。放大也是一种算法，用于多次执行随机算法的某些部分以增加正确性的概率。但是，过度的放大也会超过时间限制，从而使算法无效。
Classification of Randomized Algorithms
随机算法的分类取决于它们是否具有时间限制作为随机变量或确定性值。它们被设计为它们的两种常见形式 - 拉斯维加斯和蒙特卡罗。
-
拉斯维加斯 - 拉斯维加斯方法的随机算法永不提供错误输出，从而使时间限制成为随机变量。例如，在字符串匹配算法中，拉斯维加斯算法在遇到错误后从头开始。这增加了正确性的概率。例如随机快速排序算法。
-
蒙特卡罗 - 蒙特卡罗方法的随机算法专注于在给定的时间限制内完成执行。因此，此方法的运行时间是确定性的。例如，在字符串匹配中，如果蒙特卡罗遇到错误，它将从同一点重新启动算法。因此，节省了时间。例如卡格最小割算法
Need for Randomized Algorithms
这种方法通常用于降低时间复杂度和空间复杂度。但关于如何增加随机性会减少运行时和存储的内存而不是增加，可能存在一些歧义；我们将使用博弈论来理解这一点。
The Game Theory and Randomized Algorithms
博弈论的基本思想实际上提供了一些模型，帮助理解博弈中决策者的互动方式。这些博弈论模型使用假设来找出博弈中参与者的决策结构。这些理论模型做出的流行假设是参与者都是理性的，并且会考虑对手参与者在博弈的特定情况下会决定做什么。我们将把这个理论应用于随机算法。
Zero-sum game
零和博弈是博弈论的数学表示。它有两个参与者，其结果对一方来说是收益，而对另一方来说是等效的损失。因此，净改善是两个参与者的状态之和，总和为零。
随机算法基于零和博弈，该博弈设计一种算法，为所有输入提供最低的时间复杂度。博弈中有两个参与者；一个设计算法，对手提供算法的输入。参与者 2 需要以这种方式提供输入，以便为他们赢得博弈收益最差的时间复杂度。而参与者 1 需要设计一种算法，该算法可在最小时间内执行给定的任何输入。
例如，考虑快速排序算法，其中主算法从选择基准元素开始。但是，如果零和博弈中的参与者将排序的列表作为输入，则标准算法将提供最坏情况的时间复杂度。因此，对基准选择进行随机化将比最坏情况下执行算法更快。但是，即使算法随机选择了第一个元素作为基准并获得了最坏情况的时间复杂度，再次用相同的输入执行它也会解决问题，因为它这次选择了另一个基准。
另一方面，对于像归并排序这样的算法，时间复杂度不依赖于输入；即使算法是随机的，时间复杂度也始终保持不变。因此， randomization is only applied on algorithms whose complexity depends on the input 。