我想为这个给定的问题提出一个递归：
考虑随机化快速排序算法的一个变体，其中枢轴是随机选取的，直到阵列以这样一种方式进行分区，即较低的子阵列L和较大的子阵列G包含阵列中3/4的元素。例如，如果随机选择的枢轴以这样一种方式对数组进行分区，即L包含1/10的元素，然后是另一个元素枢轴是随机选择的。分析此算法的预期运行时间。
起初，我把这个问题当作一个常规的快速排序问题来处理，并提出了这个重复问题，其中：
T(n) = T(3/4n) + T(n/4) + Θ(n) (where Θ(n) comes from the partition)
如果我们有一个算法，其中分割总是1/4：3/4，这将是有意义的。但我们在这里使用随机枢轴，每当分区条件不满足时，枢轴就会发生变化。我知道随机化快速排序的最坏运行时间仍然是O(n^2(，但我认为在这种情况下，最坏的情况现在不同了(比O(n^2(更糟糕的情况(。到目前为止，我走对了吗？
快速排序的时间复杂性永远不会超过O(n^2)，除非您选择了一些需要O(n)时间来选择枢轴的逻辑。
选择枢轴的最佳方式是随机元素或末端或第一个元素。
存在n/2坏枢轴。假设您从未两次选择同一枢轴(如果您选择了，最坏的情况总是选择一个坏的枢轴，即无限时间(，在最坏的情形下，您将重复划分n/2次，这导致划分阶段的Θ(n^2)复杂性。复发变为
T(n) = T(n/4) + T(3n/4) + Θ(n^2)