Jim*_*_CS 48 algorithm complexity-theory quicksort
是否有人能够提供一个"简单的英语"直观,但正式的解释是什么让QuickSort n登录？根据我的理解,它必须通过n个项目,并且它会记录n次...我不知道如何将其记入单词为什么它会执行此日志n次.
Jer*_*fin 118
这__CODE__部分来自这样一个事实:它(至少理想情况下)在每次迭代时将输入分成两半.从N个项目开始,每次打破这些项目意味着在log 2(N)迭代之后你已经减少了1个项目,此时你显然无法进一步细分它.例如,从128个项目开始,您可以分为64,32,16,8,4,2,1个项目组--7次迭代(和log 2(128)= 7).
这些迭代中的每一个都扫描整个阵列以对其进行分区,因此它们中的每一个都具有O(N)复杂度.
在两者之间,您最终得到O(log N)操作,每个操作都具有O(n)复杂度,用于O(n log n)总体复杂度.
从技术上来说,Quicksort的Big-O实际上是O(N 2).这是因为分区元素的选择足够糟糕,可能会将阵列分成一侧的一个元素,另一侧的阵列的其余部分.如果在每次迭代时发生这种情况,则需要N次迭代将其分解为每个元素的一个元素,因此对于O(N*N)整体,您将获得N个操作,每个操作的复杂度为O(N).
在一个真正的实现中,你通常会在此之前停止,但这是你能走得最远的.
Eug*_*sky 45
每个分区操作都需要O(n)次操作(数组一次传递).平均而言,每个分区将数组划分为两个部分(总计记录n个操作).总共我们有O(n*log n)操作.
即平均log n分区操作,每个分区都进行O(n)操作.
对数背后有一个关键的直觉：
在达到 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) 最坏情况行为，这是寻找更多相关信息的好地方。