algorithm - 使用快速排序算法对 K 排序数组进行排序的时间复杂度

Question

问题:

我必须分析时间复杂度以对几乎已排序的整数值列表进行排序(使用快速排序)。

我做了什么？

我已阅读 SO Q1 , SO Q2 , SO Q3和 this one .

但是，我还没有发现任何明确提到使用快速排序对 k 排序数组进行排序的时间复杂度。

由于快速排序算法的时间复杂度取决于选择主元的策略，并且由于几乎排序的数据而有可能面临最坏的情况，为了避免最坏的情况，我使用了三个值的中位数(first, middle, last) 作为引用点 here .

我怎么想的？

因为在一般情况下，快速排序算法的时间复杂度是 O(n log(n)) 并且如前所述 here , “对于 n 的任何非平凡值，分而治之算法将需要多次 O(n) 遍，即使数组几乎完全排序也是如此”，

我认为使用快速排序算法对 k 排序数组进行排序的时间复杂度是 O(n log(n))，如果最坏的情况没有发生的话。

我的问题:

如果我尝试避免最坏情况选择合适的主元，使用快速排序算法对 k 排序数组进行排序的时间复杂度是 O(n log(n))没有发生这种情况。

Answer 1

当你说快速排序的时间复杂度时，它是O(n^2)，因为默认假设最坏的情况。但是，如果您使用另一种策略来选择基准，例如随机快速排序，您的时间复杂度默认情况下仍将是 O(n^2)。但预期的时间复杂度为 O(n log(n))，因为最坏情况的发生可能性很小。所以如果你能以某种方式证明最坏的情况是 100% 保证不会发生，那么你可以说时间复杂度小于 O(n^2)，否则，默认情况下，最坏的情况是考虑过，无论多么不可能。