快速排序计算

Question

如果按降序给出了一个数字列表。按快速排序按升序排列的计算费用是多少？

Answer 1

在快速排序中，如果选择第一个元素作为partitioning..then的枢轴元素

在这种情况下，快速排序显示了它最糟糕的转换复杂度- O(n^2)。

更准确地说，当要排序的输入按递减顺序或递增顺序(如果第一个元素是枢轴元素)时，快速排序的最坏情况复杂性O(n^2)。

造成这种最坏情况的原因是，在分区之后，一个分区的大小为1，而另一个分区的大小为n-1。

所以，快速排序'n‘元素的时间T(n) =

划分'n‘元素所需的时间O(n) +快速排序’n‘元素T(n-1)所需的时间

所以，T(n) = T(n-1) + O(n)

=> T(n) = O(n^2)

请不要忘记接受这个答案。你可以随便问任何你不清楚的事情