algorithm - RANDOMIZED-QUICKSORT 的概率超过最坏情况

Question

问题来自 clrs（练习 12.4-5）

考虑对 n 个输入数字的序列进行操作的 RANDOMIZED-QUICKSORT。证明对于任何常数 k > 0，除了 O(1/n^k) 的 n! 输入排列产生 O(n lg n) 运行时间。

我怎样才能建立最坏情况的模型，并获得它的最大界限。

Answer 1

您可能需要阅读此说明以进行快速介绍。然后，您可以阅读本文（尤其是第 3.1 节）以获得详尽的解释。