2

In Cormen's own words - "The difference is that with the deterministic algorithm, a particular input can elicit that worst-case behavior. With the randomized algorithm, however, no input can always elicit the worst-case behavior."

How does adding a randomized pivot change anything, the algorithm is still gonna perform bad under some particular input and considering each kind of input equally likely this is no better than that of the standard quicksort, only difference being we don't actually know which particular input is going to cause the worst case time complexity. So why is the randomized version considered better?

4

2 回答 2

2

考虑以下版本的快速排序，我们总是选择最后一个元素作为枢轴。现在考虑以下数组：

int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};

当这个数组使用我们的快速排序版本进行排序时，它总是会选择最小的元素作为它的主元，最后一个元素。在第一次迭代中，它将像这样更改数组：

arr = [1, 8, 7, 6, 5, 4, 3, 2, 9];

现在，它将在子数组上递归：

s1 = [1, 8, 7, 6, 5, 4, 3, 2];
s2 = [9];

s1它将再次选择2作为其支点，并且只有8 和 2会互换位置。所以，以这种方式，如果我们试图制定一个递推关系，由于它的复杂性，它将是

T(n) = T(n-1) + O(n)

这对应于O(n^2)。

因此，对于这个数组，标准版本总是需要O(n^2)时间。

在随机版本中，我们首先将最后一个元素与数组中的一些随机元素交换，然后选择它作为枢轴。因此，对于给定的数组，此枢轴将随机拆分数组，很可能在中间。所以，现在的复发将是

T(n) = 2T(n/2) + O(n)

这将是O(n * Log(n))。

这就是为什么我们认为随机快速排序比标准快速排序更好，因为在随机快速排序中出现错误拆分的可能性非常低。

于 2021-05-05T04:49:32.410 回答
0

不同之处在于，使用确定性算法，特定输入可以引发最坏情况的行为。然而，使用随机算法，没有输入总是能引发最坏情况的行为。

应该澄清这意味着真正的随机算法。如果改为使用确定性伪随机算法，则故意创建的输入可能会引发最坏情况的行为。

然而，使用随机算法，没有输入总是能引发最坏情况的行为。

应该澄清这一点：即使使用真正的随机算法，仍然存在某些特定输入的可能性，这些输入可能会在使用该输入的一个或多个随机快速排序调用中引发最坏情况的行为，但没有任何输入总是会引发最坏情况在同一输入上无限次调用真正随机的快速排序的行为。

大多数单枢轴快速排序的库实现使用中位数为 3 或中位数为 9，因为它们不能依赖于对 X86 RRAND 和快速除法（用于模函数）等随机数的快速指令。如果快速排序在某种程度上是加密方案的一部分，那么可以使用真正的随机算法来避免基于时间的攻击。

于 2021-05-05T18:08:06.530 回答