快速排序精确分割是n-1？

我“用”了解Quicksort，现在..我已经弄糊涂了。我知道我错过了一些非常明显的东西，毫无疑问，Quicksort是O(nlogn)，n部分很容易看到（因为我们需要在每个级别上使用n比较来根据相应的元素移动元素，但是如何？拆分logn不该”这是n-1？例如：。快速排序精确分割是n-1？

       1, 2, 3, 4 
         1, 2    3, 4 
        1  2  3  4

我们在第一级分裂1, 2, 3, 4成1, 2和3, 4，这是一个分裂然后在我们分裂1, 2为1 and 2和3, 4到3 and 4第二级，这是2分裂，所以总共3分裂，所以n-1分裂？

我不认为这是重复的，因为我假设快速排序算法的平等分割（或者相当于分而治之算法的通用平等分割）我所要求的是直观解释为什么分裂是log(n)尽管事实上，当你计算实际的拆分调用数量它是n-1在任何通用的划分和征服alogirhtm

来源

2015-11-02 q.Then

可能的重复[直观解释为什么QuickSort是n日志n？]（http://stackoverflow.com/questions/10425506/intuitive-explanation-for-why-quicksort-is-n-log-n） –

它也很好记，实际上，在最坏的情况下，quicksort实际上是O（n^2）。它被认为是O（nlogn），如果枢轴选择得很好/它在大部分时间平均为nlogn –

好的，但我在我绘制的图中假定有相同的分区（并且这是针对任何类型的分而治之算法）然而，加起来的分裂是n-1 –

好的，在评论中做了一些澄清之后，很明显这里提到了什么。

查看拆分被调用的次数的错误，这实际上是非常不相关的。有关的是原始操作的总数。

如前所述，树的深度大约是log N.在树的每个“层”上，检查输入的所有元素（并且可以交换一些元素）。

是的，在顶层你做一次调用将数组分成两部分，然后在下一层再将每一部分分成两半，依此类推。在给定的水平上调用partition（或split，或者任何你喜欢称之为的）的数量并没有真正改变任何东西。重要的是，每次分割一些数据时，都需要查看该分区中的每个数据项。在顶层，我们有一个调用分区的例子，看看整个数组。在下一级，我们有两个调用，每个调用看一半数组。第三，我们有四个调用，每个调用都查看数组的四分之一（依此类推）。

请注意，不完美的分割不会改变我们需要在树的每个级别查看的项目数量。在树的每一层，我们需要查看所有分区中的所有项目。如果分裂不在中心，这意味着我们在树中会有多于Log（N）层，但是在树的每一层，我们仍然需要查看每个输入项。

因此，基本操作的总数是输入项的数量乘以树中的层数（在完美分区的情况下大约为N），从而给出总体复杂度O （N log N）。如果分裂是不完美的，我们仍然在树的每一级查看N个项目，但是我们有更多的层次 - 可能达到N层（给出最坏情况的复杂度）。

来源

2015-11-03 00:16:58

“平等分裂”，你得到一个平衡的二叉树。

您正在做n每次迭代比较（执行“拆分”）。

问题是你需要多少次迭代？看看你的图 - 它正在形成一个平衡的二叉树。平衡二叉树有多大？

来源

2015-11-02 23:54:36 TheGreatContini

是的我得到的平衡树的高度是log（n），但是分割函数被调用的实际次数不是log（n），它是3.我们只需要做n次比较每个级别，但我们调用分裂功能3次以创建树，或者我错了吗？ –

我认为杰里回答了你的问题，见上面的回复。 – TheGreatContini

快速排序精确分割是n-1？

回答

相关问题