logo标签列表

为什么快速排序的时间复杂度是n log n？直观解释。

algorithmcomplexity-theoryquicksort
66

有没有人能够用“简单易懂”的方式，但又正式地解释快速排序算法为什么是O(n log n)的？据我所知，快速排序需要对n个元素进行一次遍历，并且它会重复执行log n次...我不确定如何用语言表达为什么它要重复执行log n次。

7个回答
177

复杂度

快速排序会首先将输入分成两个部分：它选择一个“枢轴”值，将输入分为小于枢轴值和大于枢轴值的两部分（当然，相等于枢轴值的元素也需要放到其中一部分，但是对于基本描述来说，这并不重要）。

因为输入（定义上）没有排序，所以为了进行分割，它必须查看输入中的每个元素，因此这是一个O(N)操作。在第一次分割完输入后，它递归地对这些“块”中的每一个排序。在这两次调用之间，每个递归调用都会检查它的所有输入，因此最终会访问每个输入值（再次）。所以在第一层分区时，我们有一个调用，它检查每个输入项。在第二级别上，我们有两个分区步骤，但在这两个步骤之间，它们（再次）检查每个输入项。每个后续级别都有更多的单独分区步骤，但总体来说，每个级别的调用都会查看所有输入项。

它会一直将输入分成越来越小的部分，直到达到某个分区大小的下限。可能的最小值是每个分区中只有一个元素。

理想情况

在理想情况下，我们希望每次分区将输入分成两半。这些“半部分”可能不会完全相等，但如果我们选择好枢轴，它们应该非常接近。为了让数学计算简单，假设我们进行了完美的分区，因此每次都得到精确的一半。

在这种情况下，我们可以将其分成对数级别的部分，即以2为底，输入数量的对数。例如，给定128个输入，我们将得到64、32、16、8、4、2和1这几个分区大小。这是7个分区级别（是的，log2(128) = 7）。

因此，我们有log(N)个分区“级别”，每个级别都必须访问所有N个输入。 因此，log(N)个级别乘以每个级别的N次操作，使我们得到O(N log N)的总复杂度。

最坏情况

现在让我们重新考虑每个分区级别将输入“精确”分成一半的假设。 根据我们选择的分区元素的好坏程度，我们可能无法获得精确相等的两半。 那么最糟糕的情况是什么？ 最糟糕的情况是枢轴实际上是输入中最小或最大的元素。 在这种情况下，我们进行了O(N)个分区级别，但与其得到两个相等大小的半部分，我们得到了一个包含一个元素和一个包含N-1个元素的分区。 如果每个分区级别都发生了这种情况，我们显然会在每个分区变为单个元素之前执行O(N)个分区级别。

这给出了Quicksort的技术上正确的大O时间复杂度（大O正式指代复杂度的上限）。由于我们有O(N)个分区级别，每个级别需要O(N)步骤，因此我们最终得到O(N * N)（即O(N2)）的复杂度。

实际应用

从实际角度考虑，真正的实现通常会在实际达到单个元素的分区之前停止分区。在典型情况下，当一个分区包含10个或更少的元素时，您将停止分区并使用诸如插入排序之类的东西（因为对于少量元素来说它通常更快）。

修改算法

最近发明了Quicksort的其他修改方法（例如Introsort，PDQ Sort），这些方法防止了O(N2)的最坏情况。 Introsort通过跟踪当前的分区“级别”，并在/如果它过深时切换到堆排序来实现，堆排序比Quicksort对于典型输入来说更慢，但保证任何输入的O(N log N)的复杂度。

PDQ排序方法在这里又有了新的改进: 由于堆排序比较慢，因此它试图避免使用堆排序。为达到这个目的，如果看起来选择的枢轴值较差，它将在选择枢轴之前随机重排一些输入数据。只有当这种方法不能产生足够好的枢轴值时，它才会切换到使用堆排序。

18
谢谢您的提议。这里被接受的答案只是重申了原帖（和我）已经知道的内容（n次操作做log n次），但忽略了唯一重要的部分：为什么要做log n次？这个答案很好地解释了log项的来源，而且简洁易懂。 - Cam Jackson
2
这是最好的解释。 - huseyin
@RaikolAmaro：这些调用的深度为7。如果你将给定深度的所有调用加起来，它们一起操作所有N个元素。（第一层有2 * 128，第二层有4 * 64，以此类推）。因此，您会得到对log（N）深度的调用，并且在每个级别上，操作的总数与N成比例。 - Jerry Coffin
@JerryCoffin，我现在明白你的意思了，但我认为你在原始回答中的解释存在一些歧义。无论如何，感谢您的回答。 - Raikol Amaro
1
@RaikolAmaro：是的，可能不是完全清楚。我已经重写了它，使其更加明确。 - Jerry Coffin
显示剩余8条评论
49
每次分区操作需要O(n)个操作（对数组进行一次遍历）。平均而言，每次分区将数组分成两部分（这总共需要log n个操作）。总之，我们需要O(n * log n)个操作。
换言之，平均需要log n个分区操作，每个分区操作需要O(n)个操作。
29
给正在阅读这篇回答的人，向下滑动以获得更好的回答。 - c0degeas
我看到这个想法存在问题。考虑以下（不好的）快速排序变种：在每个时刻，我们选择数组的最大值或最小值，并且等概率使用它作为主元。平均而言，较小元素的子数组的大小将为(n-1)/2，与较大元素的子数组相同。然而，这个算法总是需要Ω(n^2)的时间才能完成。因此，平均来说每次分割都是50/50并不一定意味着算法会很快。这其中还有更多的故事。 - templatetypedef
5
对数背后的关键直觉是：
在到达1之前，您可以将数字n除以一个常数的次数为O(log n)。
换句话说，如果您看到具有O(log n)项的运行时间，则很有可能会发现某些东西反复缩小一个恒定因子。
在快速排序中，每个级别的最大递归调用大小都会缩小一个恒定因子。快速排序的工作方式是选择一个枢轴，将数组分成两个子数组：元素小于枢轴和元素大于枢轴，然后对每个子数组进行递归排序。
如果随机选择枢轴，则有50％的概率选择的枢轴将位于50％的元素中间，这意味着较大的两个子数组有50％的概率至多是原始数组的75％。 （你明白为什么了吗？）
因此，快速排序运行的O(n log n)的好直觉是：递归树中的每一层都需要O(n)的工作量，并且由于每个递归调用都有很好的机会将数组的大小至少减少25％，所以我们预计在抛弃数组元素之前会有O(log n)个层。
当然，这假设您是随机选择枢轴。许多快速排序的实现使用启发式方法来尝试获得一个不需要太多工作的好枢轴，这些实现可能会导致最坏情况下整体运行时间较差。@Jerry Coffin对这个问题的出色答案讨论了一些变化的快速排序，通过切换使用哪种排序算法保证O(n log n)的最坏情况行为，并且这是寻找更多信息的好地方。
2

嗯，它并不总是n(log n)。当所选的枢轴大约在中间时，这是性能时间。在最坏情况下，如果您选择最小或最大元素作为枢轴，则时间将为O(n^2)。

要想象'n log n'，您可以假设枢轴是最接近要排序的所有元素平均值的元素。这将把数组分成大致相同长度的两部分。在这两个部分上都应用快速排序过程。

由于每一步都会将数组长度减半，因此您需要重复此操作log n（以2为底）次，直到达到长度= 1，即一个由1个元素组成的已排序数组。

你说得没错，但不要混淆平均数和中位数。中位数是允许你将数据分成两个长度相同（+-1）的部分的关键。 - kvetis
平均数不会给出中间元素。中位数将给出中间元素/元素。答案需要修正这部分。否则很好。 - Manohar Reddy Poreddy
由于列表可能未排序，而您希望为枢轴扫描一次，因此我能想到的最好方法是对数字取平均值，并选择最接近它的数字作为枢轴。现在我们出错的地方是像1 1 1 1 1 1 1 2 864这样的输入。枢轴是2，导致不平衡。 - Russ
1
将排序算法分为两部分。第一部分是分区，第二部分是递归调用。分区的复杂度为O(N)，理想情况下递归调用的复杂度为O(logN)。例如，如果有4个输入，则会有2(log4)次递归调用。将两者相乘，得到O(NlogN)。这是一个非常基本的解释。
0
实际上，您需要找到所有N个元素（枢轴）的位置，但每个元素的最大比较次数为logN（第一个是N，第二个枢轴是N/2，第三个是N/4..假设枢轴是中位数）。
这是不正确的。首先，注意到 N + N / 2 + N / 4 + N / 8 + ... = N(1 + 1/2 + 1/4 + 1/8 + ...) <= 2N，这将给出一个超越排序障碍的界限。其次，举个反例，假设您在第一步和第二步中都选择最大的元素作为枢轴。那么放置第二个枢轴需要 N - 1 次比较，而不是 N / 2。 - templatetypedef
0
在理想情况下，第一层调用将1个元素放置在其正确的位置。第二层有2个调用，总共需要O(n)时间，但它将2个元素放置在其正确的位置。同样地，第三层将有4个调用，需要O(n)的时间，但会将4个元素放置在其正确的位置。因此，递归树的深度将为log(n)，在每个深度，所有递归调用都需要O(n)的时间。因此，时间复杂度为O(nlogn)。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接