Quicksort 精确拆分是 n-1？

Question

我 "used" 了解 Quicksort，但现在..我把自己弄糊涂了。我知道我在这里遗漏了一些非常明显的东西，毫无疑问，Quicksort 是 O(nlogn)，并且 n 部分很容易看到（因为我们需要在每个级别上使用 n 比较相应地根据枢轴移动元素，但是分裂如何logn？应该是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

Answer 1

通过"equal splits"，你得到了一个平衡的二叉树。

您在每次迭代中进行 n 次比较（以执行 "splits"）。

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

Answer 2

好的，在评论中进行了一些澄清之后，很明显这里真正问的是什么。

查看调用 split 的次数时的错误，这实际上是无关紧要的。相关的是原始操作的总数。

如前所述，树的深度大约为 log₂N。在树的每个 "layer" 处，输入的所有元素都会被检查（有些可能会被交换）。

是的，在顶层，您调用一次将数组分成两半，然后在下一层再次将数组分成两半，依此类推。在给定级别调用 partition（或 split，或任何您喜欢的称呼）的次数并没有真正改变任何东西。重要的是，每次拆分某些数据时，您都需要查看该分区中的每个数据项。在顶层，我们调用了一次查看整个数组的分区。在下一层，我们有两个调用，每个调用查看数组的一半。在第三次，我们有四个调用，每个调用查看数组的四分之一（依此类推）。

请注意，不完全拆分不会改变我们需要在树的每个级别中查看的项目数。在树的每一层，我们需要查看所有分区中的所有项目。如果分裂不在中心，这意味着我们将在树中拥有超过 Log(N) 层，但在树的每一层我们仍然必须查看每个输入项。

因此，原始操作的总数是输入项的数量乘以树中的层数（在完美分区的情况下大约为log₂N)，整体复杂度为 O(N log N)。如果分裂不完美，我们仍然会在树的每一层查看 N 个项目，但是我们有更多的层——可能多达 N 层（给出 O(N² ) 最坏情况下的复杂度）。

Quicksort 精确拆分是 n-1？

Quicksort exact splitting is n-1?

quicksort

time-complexity