快速排序复杂度计算

Question

1. 如果数组的所有元素都有相同的值，那么分区的Q值是什么？myAns: O(n^2)
2. case数组中的快速排序算法已经根据需要进行排序。myAns: O(n^2)
3. case数组中的快速排序算法已经按需求的相反顺序排序。myAns: O(n log n)
4. 假设用于快速排序的分区算法将元素划分为1-α和α，其中αα≤1/2，α为常数。推导出递推关系并计算其复杂性。myAns: O(n log n)

亦请就以下事项答覆：

讨论了用于对快速排序中的数组进行分割的Hoare分区算法，并给出了适当的例子。

Answer 1

请具体说明你将来的问题是什么。

您需要指定您正在使用的枢轴--我猜您总是使用第一个分区元素作为枢轴，在这种情况下，您对2和3的答案是正确的，但是如果您使用的是中间分区元素或随机分区元素，那么您对2的答案将是不正确的(预期的运行时为n log )。

你对4的答案是增加-阿尔法需要计算到你的复杂性分析中。如果alpha = .5，则复杂度为n log，但如果alpha = 1/ n，则复杂性为n^2。您可能也应该提供导出的递归关系。

Answer 2

1. 取决于您实现快速排序的方式。
2. 取决于支点选择策略。
3. 取决于支点选择策略。
4. 正确的。