algorithm - 随机选择枢轴的优点

Question

在快速排序中，我们可以以不同的方式选择一个枢轴值。随机选择一个枢轴值就是其中之一。它说当我们随机选择枢轴值时，它最小化了 O(n^2) 的机会。谁能解释它是如何发生的？有什么缺点吗？

Answer 1

如果预期值是所有可能输入（排列）的平均值，则随机和非随机选择都会产生一个算法，其预期运行时间为 Theta(n*log(n))。

在实践中，并非所有输入排列都是同样可能的。特别是，当挑选前置（n^2）复杂性时，您通常会被分类或几乎分类。最重要的是，如果你的挑选算法是确定性的，攻击者可以制作一个令人讨厌的排列，使你的算法成为二次方，从而实现拒绝服务。

选择随机元素作为枢轴可以防止这些非随机情况。

Answer 2

有一个数学证明，随机枢轴的预期运行时间是 Theta(n logn)。

wiki 页面对此有一个部分。