随机算法
随机算法是一种与标准算法不同的设计方法，在其部分逻辑中添加了一些随机位。它们不同于确定性算法；确定性算法遵循确定的程序，每次传递输入时都会获得相同的输出，而随机算法每次执行时都会产生不同的输出。需要注意的是，随机化的不是输入，而是标准算法的逻辑。
图 1：确定性算法
与确定性算法不同，随机化算法会将逻辑的随机位与输入一起考虑，进而有助于获得输出。
图 2：随机化算法
然而，也不能排除随机化算法提供不正确输出的可能性。因此，需要执行称为放大的过程来降低这些错误输出的可能性。放大也是一种算法，用于多次执行随机算法的某些部分，以提高正确率。然而，过度放大也可能超出时间限制，导致算法无效。
随机算法的分类
随机算法根据其随机变量或确定性值是否具有时间限制进行分类。它们有两种常见的设计形式：拉斯维加斯算法和蒙特卡洛算法。
拉斯维加斯算法−拉斯维加斯随机算法永远不会给出错误输出，这使得时间约束成为随机变量。例如，在字符串匹配算法中，拉斯维加斯算法一旦遇到错误就会从头开始。这增加了正确的概率。例如，随机快速排序算法。
蒙特卡洛− 蒙特卡洛随机算法注重在给定的时间约束内完成执行。因此，该方法的运行时间是确定性的。例如，在字符串匹配算法中，如果蒙特卡洛算法遇到错误，它会从同一点重新启动算法。从而节省时间。例如，卡格尔最小割算法
随机算法的需求
这种方法通常用于降低时间复杂度和空间复杂度。但是，关于添加随机性如何减少而不是增加运行时间和内存存储，可能存在一些模糊之处；我们将使用博弈论来理解这一点。
博弈论与随机算法
博弈论的基本思想实际上提供了一些模型来帮助理解游戏中决策者如何相互作用。这些博弈论模型使用假设来计算游戏中玩家的决策结构。这些理论模型的普遍假设是，玩家既理性，又会考虑对手玩家在特定情况下会做出什么决定。我们将把这一理论应用于随机算法。
零和博弈
零和博弈是博弈论的数学表示。它有两个玩家，结果是一个玩家获得收益，而另一个玩家则遭受同等损失。因此，净改进是两个玩家状态的总和，总和为零。
随机算法基于零和博弈，旨在设计一种对所有输入都具有最低时间复杂度的算法。游戏中有两个玩家；一个玩家设计算法，对手提供算法的输入。玩家二需要以最差时间复杂度的方式提供输入，才能赢得游戏。而玩家一需要设计一个算法，使执行任何给定输入所需的时间最少。
例如，考虑快速排序算法，其主要算法从选择枢轴元素开始。但是，如果零和博弈中的玩家选择排序后的列表作为输入，则标准算法提供最差情况的时间复杂度。因此，随机化枢轴选择将使算法的执行速度比最差时间复杂度更快。然而，即使算法随机选择第一个元素作为主元并获得最差的时间复杂度，使用相同输入再次执行该算法仍能解决问题，因为这次算法选择了另一个主元。
另一方面，对于像合并排序这样的算法，时间复杂度并不依赖于输入；即使算法是随机的，时间复杂度也始终保持不变。因此，随机化仅适用于复杂度取决于输入的算法。
示例
一些流行的随机化算法示例如下：−
