If you're seeing this message, it means we're having trouble loading external resources on our website.

如果你被网页过滤器挡住,请确保域名*.kastatic.org*.kasandbox.org 没有被阻止.

主要内容

快速排序分析

快速排序的最坏情况和平均情况下的运行时间有什么不同?让我们先来看看最坏的情况下的运行时间。假设我们真的很不走运,分区大小真的不平衡。特别是,假设 分区 函数选择的枢轴始终是 n-元素子数组中最小或最大的元素。然后其中一个分区将不包含任何元素,另一个分区将包含 n1 元素,除数据透视外,所有分区都将包含。因此,递归调用将位于大小为0和 n1 的子数组上。
与合并排序一样,n -element子数组上给定递归调用的时间是Θ(n)。 在合并排序中,这是合并的时间,但在快速排序中,它是分区的时间。

最糟糕的运行时间

当quicksort总是拥有最不平衡的分区时,原始调用需要cn时间来获得一些常量cn1元素的递归调用需要cn1 time,递归调用 在n2元素上需要cn2 time,依此类推。 这是一个子问题大小的树及其分区时间:
快速排序最坏情况的图,图左边是树,右边是分区时间。树标为“子问题大小”,右侧标为“这个大小的所有子问题的总分区时间”。 树的第一级显示一个节点 n 和相应的分区时间,即 c 乘以 n 。树的第二级显示两个节点,0 和 n 减 1,分区时间为 c 乘以 n 减 1。树的第三级显示有两个节点,0 和 n 减 2,分区时间为 c 乘以 n 减 2。树的第四级显示有两个节点,0 和 n 减 3,分区时间为 c 乘以 n 减 3。这一级以下,显示了一些点来表示这个树以相同方式延续下去。倒数第二级显示了 1 个节点 2,且分区时间是 2 乘以 c,而最后一级有两个节点 0 和 1,分区时间为 0。
当我们汇总每个级别的分区时间时,我们将获得
cn+c(n1)+c(n2)++2c=c(n+(n1)+(n2)++2)=c((n+1)(n/2)1) .
最后一行是因为1+2+3++n是算术系列,正如我们在分析选择排序时所看到的那样(我们减1,因为对于quicksort,求和从2开始,而不是1.)我们有一些低阶项和常系数,但是当我们使用big-Θ表示法时,我们忽略它们。 在big-Θ表示法中,quicksort的最坏情况运行时间为Θ(n2)

最佳的运行时间

当分区尽可能均衡时,Quicksort的最佳情况是:它们的大小相等或彼此相差1。 前一种情况发生在子阵列具有奇数个元素且分区后枢轴位于中间的情况下,并且每个分区具有n1/2个元素。 如果子阵列具有偶数n元素并且一个分区具有n/2元素而另一个具有n/21,则发生后一种情况。 在这两种情况中,每个分区最多只有n/2个元素,子问题大小的树看起来很像合并排序的子问题大小树,分区时间看起来像合并时间:
快速排序的最佳情况,树在左侧和分区时间在右侧的图。树标为“子问题大小”,右侧标为“这个大小的所有子问题的总分区时间”。 树的第一级显示一个节点 n 和相应的分区时间,即 c 乘以 n 。树的第二级显示两个节点,均小于或等于 1/2 n,分区时间为小于或等于 2 乘以 c 再乘以 1/2 n,结果与 c 乘以 n 相同。树的第三级显示有四个节点,均小于或等于 1/4 n,而分区时间为 4 乘以 c 再乘以 1/4 n,也与 c 乘以 n 相同。树的第四级显示有八个节点,均小于或等于 1/8 n,而分区时间为 8 乘以 c 再乘以1/8 n,也与 c 乘以 n 相同。这一级以下,显示了一些点来表示这个树以相同方式延续下去。最后一级显示了 n 个 1 节点,且分区时间小于或等于 n 乘以 c,与 c 乘以 n 相同。
使用大表示法, 我们得到相同的结果合并排序:Θ(nlog2n).

平均运行时间

显示平均情况下的运行时间也是 Θ(nlog2n)需要一些非常复杂的数学,所以我们不会去那里。 但是我们可以通过查看其他几个案例来了解为什么它可能是O(nlog2n)。 (一旦我们有O(nlog2n)Θ(nlog2n)范围就会跟随,因为平均情况下的运行时间不能好于最佳运行时间。) ,让我们想象一下,我们并不总是得到均匀平衡的分区,但我们总是得到最差的3比1分割。 也就是说,想象一下,每次分区时,一方获得3n/4 元素,另一方获得n/4.。 (为了保持数学清晰,让我们不要担心枢轴。)然后子问题大小和分区时间的树将如下所示:
快速排序的平均性能图
每个节点的左子节点大小为1/4的子问题,右子节点大小为3/4的子问题。由于较小的子问题在左侧,通过遵循左子路径,我们从根向下到达比其他任何路径快1的子问题。如图所示,在log4n 级别之后,我们得到的子问题大小为1 。为什么log4n级别?考虑从子问题大小1开始并将其乘以4直到达到n,这可能是最容易的。换句话说,我们要求x的值是4x=n?答案是log4n。走向正确的孩子的道路怎么样?该图表明,需要log4/3n级才能达到大小为1 的子问题。为什么log4/3n级别?由于每个右子节点是其上方节点(其节点)大小的3/4,因此每个父节点的大小是其右子节点的4/3倍。让我们再次考虑从大小为1的子问题开始,然后将大小乘以4/3,直到达到nx的值是4/3x=n?答案是log4/3n
在每个第一个log4n级别中,有n节点(再次,包括实际上不再被分区的枢轴),因此每个级别的总分区时间为cn。 但其他级别呢? 每个节点都少于n节点,因此 每个 级别都 最多 cn。 总共有log4/3n 级别,因此总分区时间为O(nlog4/3n)。 现在,有一个数学事实
logan=logbnlogba
所有正数 ab n a = 4 元和 b=2, 我们得到的是
log4/3n=log2nlog2(4/3) ,
所以log4/3nlog2n 只相差log2(4/3),这是一个常数。 由于当我们使用big-O表示法时常数因素无关紧要,我们可以说如果所有拆分都是3比1,那么quicksort的运行时间是O(nlog2n),尽管有更大的 隐藏的常数因素比最佳情况下的运行时间。
我们应该多久预期会看到3比1或更好的分割? 这取决于我们如何选择枢轴。 让我们想象一下,在分区之后,枢轴同样可能最终在n -element子数组中的任何位置。 然后要获得3比1或更好的分割,枢轴必须位于“中间半部分”的某个位置:
因此,如果在分区之后枢轴同样可能在子阵列中的任何位置结束,则有50%的可能性在最坏情况下以3比1的分割。 换句话说,我们预计分成3比1或更好的时间约为一半。
另一种情况我们将会了解为什么quicksort的平均案例运行时间是O(nlog2n) ,如果我们没有得到3比1的一半时间会发生什么 分裂,我们得到了最糟糕的分裂。 让我们假设3对1和最坏情况的拆分交替,并考虑树中的节点,其子阵列中有k元素。 然后我们会看到树的一部分看起来像这样:
而不是像这样:
因此,即使我们将最坏情况下的分割时间缩短了一半,并且分割时间为3比1或更好的一半,运行时间大约是每次进行3比1分割的运行时间的两倍。。 同样,这只是一个常数因素,它被吸收到大O符号中,所以在这种情况下,我们在最坏情况和3对1分裂之间交替,运行时间是O(nlog2n)
请记住,这种分析在数学上 并不 严谨,但它让您直观地了解为什么平均情况下的运行时间可能是O(nlog2n).

随机快速排序

假设你的最大敌人给你一个数组来使用快速排序进行排序,知道你总是选择每个子阵列中最右边的元素作为枢轴,并安排了数组,以便你 总是 得到最坏情况的分裂。 你怎么能欺骗你的敌人?
您不一定要选择每个子阵列中最右边的元素作为枢轴。 相反,您可以随机选择子阵列中的元素,并将该元素用作轴。 但是等待分区函数假定枢轴位于子阵列的最右边位置。 没问题 - 只需将您选择的元素与最右边的元素交换为枢轴,然后像以前一样进行分区。 除非你的敌人知道你如何选择子阵列中的随机位置,否则你就赢了!
事实上,通过更多的努力,你可以提高你在最坏的情况下获得3比1的分裂机会。从子阵列中随机选择一个,但不是三个元素,并将三个中间值作为枢轴(用最右边的元素交换)。通过中位数,我们指的是三个元素的值在中间。我们不会显示原因,但如果您选择三个随机选择的元素的中位数作为支点,则您有68.75%的几率(11/16)获得3比1的分割或更好。你可以走得更远。如果您随机选择五个元素并将中位数作为支点,那么在最差的情况下,3比1分割的几率提高到约79.3%(203/256)。如果你取七个随机选择的元素的中位数,它会上升到大约85.9%(1759/2048)。九个中位数?约90.2%(59123/65536)。 11的中位数?约93.1%(488293/524288)。你得到了照片。当然,随机选择大量元素并取其中位数并不一定是值得的,因为这样做的时间几乎可以抵消获得良好分散的好处。

本内容是 达特茅斯计算机科学 教授 Thomas CormenDevin Balkcom,与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA

想加入讨论吗?

尚无帖子。
你会英语吗?单击此处查看更多可汗学院英文版的讨论.