algorithm - 快速排序复杂度计算

Question

1. 如果数组的所有元素都具有相同的值，快速排序分区返回的 q 值是多少？ myAns:O(n^2)
2. 快速排序算法，以防数组已按要求排序。 myAns:O(n^2)
3. 快速排序算法，以防数组已经按要求的相反顺序排序。 myAns:O(n log n)
4. 假设用于快速排序的划分算法将元素划分为 1-α 和 α，其中 0< α ≤1/2，α 是常数。推导递推关系并计算其复杂度。 myAns:O(n log n)

请同时回答:

用适当的例子讨论用于划分快速排序中使用的数组的 Hoare 分区算法。

Answer 1

请说明您以后的问题是什么。

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

您对 4 的回答是错误的 - alpha 需要计入您的复杂性分析。如果 alpha = .5 则复杂度为 n log n，但如果 alpha = 1/n 则复杂度为 n^2。您可能还应该提供您导出的递归关系。