algorithm - 有人可以澄清快速排序和随机快速排序之间的区别吗？

Question

如果我选择随机主元与仅选择无序集合/列表中的第一个主元有何不同？

如果集合是无序的，选​​择集合中的第一个值本身不是随机的吗？因此，从本质上讲，我试图了解随机化如何/是否 promise 更好的最坏情况运行时间。

Answer 1

我认为您可能混淆了任意 和随机 的概念。选择数组的第一个元素是任意的 - 您可以选择任何您喜欢的元素，它同样有效 - 但它不是随机的。 随机的选择是无法提前预测的。一个任意的选择是可以的。

假设您正在对排序序列 1、2、3、4、5、6、...、n 使用快速排序。如果您选择第一个元素作为基准，那么您将选择 1 作为基准。然后所有 n - 1 个其他元素都向右移动，没有任何元素向左移动，您将递归地对 2、3、4、5、...、n 进行快速排序。

当您对该范围进行快速排序时，您将选择 2 作为基准。然后对元素进行分区，左边什么都不放，右边放数字 3、4、5、6、...、n，所以你将递归地对 3、4、5、6、...、n 进行快速排序。

更一般地，在 k 步之后，您将选择数字 k 作为主元，将数字 k+1、k+2、...、n 放在右边，然后递归地对它们进行快速排序。

这里完成的总工作量最终为 Θ(n²)，因为在第一遍(分区 2、3、...、n 大约 1)中，您必须查看 n -1 个元素，在第二遍(划分到 3、4、5、...、n 左右 2)时，你必须查看 n-2 个元素，等等。这意味着完成的工作是 (n-1) +(n-2)+ ... +1 = Θ(n²)，效率很低!

现在，将其与随机快速排序进行对比。在随机快速排序中，您真正选择了一个随机元素作为每一步的基准。这意味着虽然您在技术上可以选择与确定性情况下相同的枢轴，但这不太可能(概率大约为 2^{2 - n}，这是非常低的)这会发生并触发最坏情况的行为。您更有可能选择更靠近数组中心的枢轴，当发生这种情况时，递归分支会更均匀，因此终止得更快。

随机快速排序的优点是没有一个输入总是会导致它在时间 Θ(n log n) 内运行，并且运行时间预计为 O(n log n)。确定性快速排序算法通常有以下缺点:(1) 它们在最坏情况下运行时间为 O(n log n)，但常数因子很高，或者 (2) 它们在最坏情况下运行时间为 O(n ²) 并且触发这种情况的输入类型是确定性的。