我开始知道，在随机快速排序的情况下，如果我们以这样一种方式选择枢轴，它至少会给出 25%-75% 的比例分配，那么运行时间是O(n log n). 现在我也开始知道我们可以用 Master Theorem 证明这一点。
但我的问题是，如果我们在每一步中将数组拆分为 25%-75%，那么我将如何定义我的T(n)以及如何证明运行时分析O(n log n)？
问问题
840 次
1 回答
2
您可以使用Master theorem找出这种算法的复杂性。在这种特殊情况下，假设当您将数组分成两部分时，这些部分中的每一个都不大于初始数组的 3/4。然后，T(n) < 2 * T(3/4 * n) + O(n)，或者T(n) = 2 * T(3/4 * n) + O(n)如果您寻找上限。Master theorem 给你这个方程的解。
更新：虽然 Master theorem 可以解决这样的递归方程，但在这种情况下，它给我们的结果比预期的 O(n*log n) 更差。不过，也可以通过其他方式解决。如果我们假设枢轴总是以较小的部分 >= 1/4 大小的方式拆分数组，那么我们可以将递归深度限制为 log_{4/3}N（因为在每个级别上，数组的大小都会减小至少 4/3 倍）。每个递归级别的时间复杂度总共为 O(n)，因此我们有 O(n) * log{4/3}n = O(n*log n) 整体复杂度。
此外，如果您想要更严格的分析，您可以考虑维基百科的文章，有一些很好的证明。
于 2013-07-22T19:05:19.240 回答