logo标签列表

快速排序复杂度深入解析

algorithmtime-complexityquicksortpartitionlogarithm
3
所以我正在参加一场考试，其中一个重要部分是快速排序算法。众所周知，这个算法的最佳情况和实际上的平均情况是：O(nlogn)。最坏情况是O(n^2)。
至于最坏情况，我知道如何解释它：当选择的枢轴是数组中最小或最大的值时，我们会有n个快速排序调用，每个调用可能需要n时间（我的意思是划分操作）。我是对的吗？
现在是最好/平均情况。我读过Cormen的书，由于那本书，我理解了很多东西，但是对于快速排序算法，他专注于数学公式来解释O(nlogn)复杂度。我只想知道为什么它是O(nlogn)，而不涉及某些数学证明。目前我只看到维基百科的解释，即如果我们选择将我们的数组分成n/2, n/2+1两部分，那么我们将有一个深度为logn的调用树，但我不知道这是否正确，即使是这样，为什么是logn。
我知道互联网上有许多涵盖快速排序的材料，但它们只涵盖实现，或者只是告诉我复杂度，而不解释它。
1
你理解log2是什么吗？你理解每一层递归将剩余工作分成两半的影响吗？ - Dave S
是的，我必须找到一个数字k，使得2^k=n。 - minecraftplayer1234
是的，所以如果你走n、n/2、n/4、n/8…，根据定义，会有log2(n)个项。 - Bernhard Barker
每个都需要n的时间，对吧？ - minecraftplayer1234
2个回答
1

我是不是正确？

是的。

我们将会得到一棵深度为logn的调用树，但我不知道这是否正确。

是的。

为什么是logn？

因为我们在每一步中把数组分成两半，导致调用图的深度为logn。参考Intro。

enter image description here

看看这棵树及其深度，它是logn。将其想象为在BST中的搜索成本为logn，或者为什么在已排序数组中进行二分查找也需要logn。

PS：数学说出真相，投资于理解它们，你将成为更好的计算机科学家！=）

1
对于最好情况，快速排序将当前数组在每个分区步骤上平均分割为50％/50％（一半），时间复杂度为O（log2（n））（1 / .5 = 2），但忽略常数2，因此它是O（n log（n））。
如果每个分区步骤产生20％/ 80％的分割，则最坏情况时间复杂度将基于80％或O（n log1.25（n））（1 / .8 = 1.25），但忽略常数1.25，因此它也是O（n log（n）），即使对于排序100万个元素而言，它比50％/ 50％分区情况要慢大约3倍。
当分区拆分仅每次线性减少分区大小时，时间复杂度为O（n ^ 2）。最简单且最差的情况示例是每个分区步骤仅删除1个元素。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接