设计和分析 - 随机算法

随机算法是标准算法采用的一种不同的设计方法，其中很少有随机位被添加到其逻辑的一部分中。它们与确定性算法不同；确定性算法遵循明确的过程，以便每次传递输入时都获得相同的输出，而随机算法每次执行时都会产生不同的输出。需要注意的是，随机化的不是输入，而是标准算法的逻辑。

确定性算法

图 1：确定性算法

与确定性算法不同，随机算法考虑逻辑的随机位以及输入，这反过来又有助于获得输出。

随机算法

图 2：随机算法

然而，也不能排除随机算法提供不正确输出的可能性。因此，执行称为放大的过程来减少这些错误输出的可能性。放大也是一种算法，用于多次执行随机算法的某些部分，以增加正确的概率。然而，过多的放大也会超出时间限制，导致算法无效。

随机算法的分类

随机算法根据其是否具有随机变量或确定性值的时间约束进行分类。它们以两种常见的形式设计——拉斯维加斯和蒙特卡洛。

分类_随机_算法

  • 拉斯维加斯- 拉斯维加斯随机算法方法永远不会给出不正确的输出，使时间约束成为随机变量。例如，在字符串匹配算法中，拉斯维加斯算法一旦遇到错误就从头开始。这增加了正确的可能性。例如，随机快速排序算法。

  • 蒙特卡罗- 随机算法的蒙特卡罗方法侧重于在给定的时间限制内完成执行。因此，该方法的运行时间是确定的。例如，在字符串匹配中，如果蒙特卡罗遇到错误，它会从同一点重新开始算法。从而节省时间。例如，Karger 的最小割算法

需要随机算法

通常采用这种方法来降低时间复杂度和空间复杂度。但是，关于添加随机性如何减少而不是增加运行时间和存储的内存可能存在一些模糊性；我们将使用博弈论来理解这一点。

博弈论和随机算法

博弈论的基本思想实际上提供了很少的模型来帮助理解博弈中的决策者如何相互作用。这些博弈论模型使用假设来确定博弈中玩家的决策结构。这些理论模型做出的流行假设是，玩家都是理性的，并且会考虑对手玩家在游戏的特定情况下会决定做什么。我们将把这个理论应用到随机算法上。

零和博弈

零和博弈是博弈论的数学表述。它有两名玩家，其中一名玩家的结果是收益，而另一名玩家的结果是同等的损失。因此，净改进是两名球员状态的总和，总和为零。

随机算法基于设计一种算法的零和游戏，该算法为所有输入提供最低的时间复杂度。游戏中有两名玩家；一方设计算法，对手提供算法的输入。玩家二需要以这样的方式给出输入，这将为他们赢得游戏带来最差的时间复杂度。然而，玩家需要设计一种算法，以最少的时间来执行任何给定的输入。

例如，考虑快速排序算法，其中主要算法从选择主元元素开始。但是，如果零和游戏中的玩家选择排序列表作为输入，则标准算法提供最坏情况的时间复杂度。因此，随机化主元选择将比最差时间复杂度更快地执行算法。然而，即使算法随机选择第一个元素作为主元并获得最差的时间复杂度，使用相同的输入再次执行它也会解决问题，因为它这次选择了另一个主元。

另一方面，对于像归并排序这样的算法，时间复杂度并不取决于输入；而是取决于输入。即使算法是随机的，时间复杂度也将始终保持不变。因此，随机化仅适用于复杂性取决于输入的算法。