algorithm - 具有 25%-75% 拆分的随机快速排序枢轴选择

Question

我开始知道，在随机快速排序的情况下，如果我们以这样的方式选择主元，它至少会给出 25%-75% 的比例拆分，那么运行时间是 O (n log n)。现在我也知道我们可以用大定理来证明这一点。

但我的问题是，如果我们在每一步中将数组拆分为 25%-75%，那么我将如何定义我的 T(n) 以及我如何证明运行时分析在O(n log n)?

Answer 1

您可以使用 Master theorem找出这种算法的复杂性。在这种特殊情况下，假设当您将数组分成两部分时，每个部分都不大于初始数组的 3/4。然后，T(n) < 2 * T(3/4 * n) + O(n) , 或 T(n) = 2 * T(3/4 * n) + O(n)如果你寻找上限。主定理为您提供了该方程的解。

更新:尽管主定理可以解决此类递归方程，但在这种情况下，它给我们的结果比预期的 O(n*log n) 更糟。尽管如此，它可以通过其他方式解决。如果我们假设一个主元总是以较小的部分 >= 1/4 大小的方式拆分数组，那么我们可以将递归深度限制为 log_{4/3}N (因为在每个级别上数组的大小都会减少至少 4/3 倍)。每个递归级别的时间复杂度总共为 O(n)，因此我们的总体复杂度为 O(n) * log{4/3}n = O(n*log n)。

此外，如果你想要更严格的分析，你可以考虑一个Wikipedia文章，有一些很好的证明。