Data Structures Algorithms 简明教程
Randomized Algorithms
随机算法是一种不同的设计方法，该方法是由标准算法采用的，其中少量随机位被添加到其逻辑的部分。它们不同于确定性算法；确定性算法遵循确定的过程以在每次输入通过时获得相同的输出，而随机算法则在每次执行时生成不同的输出。值得注意的是，被随机化的不是输入，而是标准算法的逻辑。
Randomized algorithm is a different design approach taken by the standard algorithms where few random bits are added to a part of their logic. They are different from deterministic algorithms; deterministic algorithms follow a definite procedure to get the same output every time an input is passed where randomized algorithms produce a different output every time they’re executed. It is important to note that it is not the input that is randomized, but the logic of the standard algorithm.
Figure 1: Deterministic Algorithm
Figure 1: Deterministic Algorithm
与确定性算法不同，随机算法考虑逻辑的随机位与有助于获得输出的输入。
Unlike deterministic algorithms, randomized algorithms consider randomized bits of the logic along with the input that in turn contribute towards obtaining the output.
Figure 2: Randomized Algorithm
Figure 2: Randomized Algorithm
但是，也不能排除随机算法提供错误输出的可能性。因此，执行称为 amplification 的过程以减少这些错误输出的可能性。放大也是一种算法，用于多次执行随机算法的某些部分以增加正确性的概率。但是，过度的放大也会超过时间限制，从而使算法无效。
However, the probability of randomized algorithms providing incorrect output cannot be ruled out either. Hence, the process called amplification is performed to reduce the likelihood of these erroneous outputs. Amplification is also an algorithm that is applied to execute some parts of the randomized algorithms multiple times to increase the probability of correctness. However, too much amplification can also exceed the time constraints making the algorithm ineffective.
Classification of Randomized Algorithms
随机算法的分类取决于它们是否具有时间限制作为随机变量或确定性值。它们被设计为它们的两种常见形式 - 拉斯维加斯和蒙特卡罗。
Randomized algorithms are classified based on whether they have time constraints as the random variable or deterministic values. They are designed in their two common forms − Las Vegas and Monte Carlo.
-
*Las Vegas *− The Las Vegas method of randomized algorithms never gives incorrect outputs, making the time constraint as the random variable. For example, in string matching algorithms, las vegas algorithms start from the beginning once they encounter an error. This increases the probability of correctness. Eg., Randomized Quick Sort Algorithm.
-
*Monte Carlo *− The Monte Carlo method of randomized algorithms focuses on finishing the execution within the given time constraint. Therefore, the running time of this method is deterministic. For example, in string matching, if monte carlo encounters an error, it restarts the algorithm from the same point. Thus, saving time. Eg., Karger’s Minimum Cut Algorithm
Need for Randomized Algorithms
这种方法通常用于降低时间复杂度和空间复杂度。但关于如何增加随机性会减少运行时和存储的内存而不是增加，可能存在一些歧义；我们将使用博弈论来理解这一点。
This approach is usually adopted to reduce the time complexity and space complexity. But there might be some ambiguity about how adding randomness will decrease the runtime and memory stored, instead of increasing; we will understand that using the game theory.
The Game Theory and Randomized Algorithms
博弈论的基本思想实际上提供了一些模型，帮助理解博弈中决策者的互动方式。这些博弈论模型使用假设来找出博弈中参与者的决策结构。这些理论模型做出的流行假设是参与者都是理性的，并且会考虑对手参与者在博弈的特定情况下会决定做什么。我们将把这个理论应用于随机算法。
The basic idea of game theory actually provides with few models that help understand how decision-makers in a game interact with each other. These game theoretical models use assumptions to figure out the decision-making structure of the players in a game. The popular assumptions made by these theoretical models are that the players are both rational and take into account what the opponent player would decide to do in a particular situation of a game. We will apply this theory on randomized algorithms.
Zero-sum game
Zero-sum game
零和博弈是博弈论的数学表示。它有两个参与者，其结果对一方来说是收益，而对另一方来说是等效的损失。因此，净改善是两个参与者的状态之和，总和为零。
The zero-sum game is a mathematical representation of the game theory. It has two players where the result is a gain for one player while it is an equivalent loss to the other player. So, the net improvement is the sum of both players’ status which sums up to zero.
随机算法基于零和博弈，该博弈设计一种算法，为所有输入提供最低的时间复杂度。博弈中有两个参与者；一个设计算法，对手提供算法的输入。参与者 2 需要以这种方式提供输入，以便为他们赢得博弈收益最差的时间复杂度。而参与者 1 需要设计一种算法，该算法可在最小时间内执行给定的任何输入。
Randomized algorithms are based on the zero-sum game of designing an algorithm that gives lowest time complexity for all inputs. There are two players in the game; one designs the algorithm and the opponent provides with inputs for the algorithm. The player two needs to give the input in such a way that it will yield the worst time complexity for them to win the game. Whereas, the player one needs to design an algorithm that takes minimum time to execute any input given.
例如，考虑快速排序算法，其中主算法从选择基准元素开始。但是，如果零和博弈中的参与者将排序的列表作为输入，则标准算法将提供最坏情况的时间复杂度。因此，对基准选择进行随机化将比最坏情况下执行算法更快。但是，即使算法随机选择了第一个元素作为基准并获得了最坏情况的时间复杂度，再次用相同的输入执行它也会解决问题，因为它这次选择了另一个基准。
For example, consider the quick sort algorithm where the main algorithm starts from selecting the pivot element. But, if the player in zero-sum game chooses the sorted list as an input, the standard algorithm provides the worst case time complexity. Therefore, randomizing the pivot selection would execute the algorithm faster than the worst time complexity. However, even if the algorithm chose the first element as pivot randomly and obtains the worst time complexity, executing it another time with the same input will solve the problem since it chooses another pivot this time.
另一方面，对于像归并排序这样的算法，时间复杂度不依赖于输入；即使算法是随机的，时间复杂度也始终保持不变。因此， randomization is only applied on algorithms whose complexity depends on the input 。
On the other hand, for algorithms like merge sort the time complexity does not depend on the input; even if the algorithm is randomized the time complexity will always remain the same. Hence, randomization is only applied on algorithms whose complexity depends on the input.