当所有元素都相同时,Quicksort的复杂性如何?
我有一个N个数字相同的数组。我正在对其应用快速排序。在这种情况下,排序的时间复杂度应该是多少。
我围绕这个问题进行了调查,但没有得到确切的解释。
任何帮助,将不胜感激。
回答:
这取决于Quicksort的实现。划分为两个(<
和>=
)部分的传统实现将具有O(n*n)
相同的输入。尽管不一定会发生 交换
,但它将导致进行n
递归调用-每个调用都需要与数据透视图和n-recursionDepth
元素进行比较。即O(n*n)
需要进行比较
然而,有一个简单的变体,其分区分为3组(<
,=
和>
)。O(n)
在这种情况下,此变体具有性能-
与其选择枢轴,不进行交换,然后递归0
到pivotIndex-1
and pivotIndex+1
to
n
,它将将与枢轴相等的所有事物都放置到“中间”分区(在所有相同输入的情况下,总是意味着本身进行交换(即无操作)意味着在这种特殊情况下,n次比较调用堆栈的深度仅为1,并且不会发生交换。我相信这种变种至少已经进入了Linux上的标准库。
以上是 当所有元素都相同时,Quicksort的复杂性如何? 的全部内容, 来源链接: utcz.com/qa/406463.html