当所有元素相同时,Quicksort的复杂性？

Question

当所有元素相同时,Quicksort的复杂性？

San*_*hak 17 c algorithm complexity-theory

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

我瞥了一眼这个问题,但没有得到确切的解释.

任何帮助,将不胜感激.

Answer 1

这取决于Quicksort的实现.分成2(<和>=)部分的传统实现将具有O(n*n)相同的输入.虽然不会发生交换,但它会导致n递归调用 - 每个调用都需要与pivot和n-recursionDepth元素进行比较.即O(n*n)需要进行比较

然而,有一个简单的变体,分为3组(<,=和>).这种变体具有O(n)的性能在这种情况下-而不是选择的支点,交换然后迭代上0,以pivotIndex-1和pivotIndex+1到n,就会把掉所有的东西等于支点的"中间"分区(在所有相同的输入总是手段的情况下自我交换,即无操作)意味着在这种特殊情况下调用堆栈只有1深度n比较并且不会发生交换.我相信这个变种至少已经进入linux上的标准库.

我认为Hoare的原始分区包含`<=`和`> =`部分，并在它们之间均匀分配相等的值。在平均情况下（不同的数据），这没有成本，并且在数据相等的情况下，可以保证O（N log N）个时间 (2认同)

Answer 2

ltj*_*jax 5

快速排序的性能取决于枢轴选择.选择的枢轴越接近中间元素,快速排序的性能越好.

在这种特殊情况下,你是幸运的-你选择的支点将永远是一个中位数,因为所有的值都是一样的.因此,快速排序的分区步骤将永远不必交换元素,并且两个指针将恰好在中间相遇.因此,这两个子问题的大小只有一半 - 给你一个完美的O(n log n).

更具体一点,这取决于分区步骤的实现情况.循环不变只需要确保较小的元素在左手子问题中,而较大的元素在右手子问题中.无法保证分区实现永远不会交换相同的元素.但它总是不必要的工作,所以没有聪明的实现应该这样做:left和right指针永远不会检测到相应的枢轴反转(即你永远不会遇到这种情况*left > pivot && *right < pivot),因此left指针将递增,right指针将每减少一次步骤,他们将最终在中间相遇,产生大小的子问题n/2.

因为QuickSort的大多数实现在他正在讨论的特定情况下实际上具有"n*n"性能 - 所有元素都相同. (5认同)
因为他们一般是基于`<`和`>=`进行分区，所以虽然不会发生交换，但会递归`n*n`次，每次都递归，仍然导致`n*n`性能 (2认同)
@tobyodavies:我相信,如果没有为quicksort正确实施.你必须向我展示一个没有的流行实现.例如,快速排序的VS2010实现(这是std :: sort中使用的introsort的'部分')甚至为它选择的枢轴建立了"相等范围",并且在这种特定情况下将给出线性复杂性. (2认同)
我不认为_real_ quicksort有一个严格的定义.它更像是一个算法模板.它基本上是:选择枢轴,分区,递归子问题.如果你正确地执行所有步骤(从某种意义上说,复杂性不会不必要地上升),这种情况下的复杂性将不是二次的(理论上和实际上).例如,如果你只是实现`<`和`> =`,你甚至可以使用equals-elements情况获得无限递归.(所有元素将始终位于右侧,子问题永远不会缩小). (2认同)

归档时间：	14 年，9 月前
查看次数：	32350 次
最近记录：	10 年，7 月前