当所有元素都相同时,Quicksort的复杂性如何?

我有一个N个数字相同的数组。我正在对其应用快速排序。在这种情况下,排序的时间复杂度应该是多少。

我围绕这个问题进行了调查,但没有得到确切的解释。

任何帮助,将不胜感激。

回答:

这取决于Quicksort的实现。划分为两个(<>=)部分的传统实现将具有O(n*n)相同的输入。尽管不一定会发生 交换

,但它将导致进行n递归调用-每个调用都需要与数据透视图和n-recursionDepth元素进行比较。即O(n*n)需要进行比较

然而,有一个简单的变体,其分区分为3组(<=>)。O(n)在这种情况下,此变体具有性能-

与其选择枢轴,不进行交换,然后递归0pivotIndex-1and pivotIndex+1to

n,它将将与枢轴相等的所有事物都放置到“中间”分区(在所有相同输入的情况下,总是意味着本身进行交换(即无操作)意味着在这种特殊情况下,n次比较调用堆栈的深度仅为1,并且不会发生交换。我相信这种变种至少已经进入了Linux上的标准库。

以上是 当所有元素都相同时,Quicksort的复杂性如何? 的全部内容, 来源链接: utcz.com/qa/406463.html

回到顶部