algorithm - Quick Sort when pivot 的时间复杂度(split list into 90% :10%) (always smallest element for even depth)

Question

下面2种情况下quicksort的时间复杂度是多少:

1. Pivot 始终将列表分成 9:1 的比例
2. 枢轴始终是偶数深度的最小元素(最坏情况)和奇数深度的中间元素(最佳情况)。

对于 1，我想我们有递归方程:

F(N) = F(N/10) + F(9N/10) + N

对于 2，

F(N) = F(N-1) + N if even
F(N) = 2*F(N/2) + N if odd

我对这些方程是否正确？如何求解这两个递归方程？

Answer 1

你的公式是正确的，这两种情况都会给你一个 O(nlogn) 复杂度。

第一个证明:

如果您为第一种情况编写递归树，您将看到从每个节点，您将分支到一个节点，该节点是当前问题大小的1/10，而另一个节点是等于当前问题大小的 9/10。

很直观，左边的分支将首先到达基本情况(因为我们在这个分支中使用了问题的较小部分)，因此更大的复杂性将出现在右边的分支中。

每次你走对了，你将解决一个较小的问题，它是它上方问题(其父级)的 9/10 大小。所以问题是，这样一棵树的深度是多少(我可以将我的问题除以 10/9 的因子多少次)

不难看出答案是:

log(10/9) N

在树的每一层我们都必须遍历 N 个值(即整个数组或向量)，因此时间复杂度为:

N * log(10/9) N = N * (log(2) N/log(10/9)

但是log(10/9)只是一个很小的常量，因此时间复杂度是:

N * log(2) N

第二个证明

它与另一个非常相似，在这种情况下，递归树的深度将是完美快速排序情况的两倍(当我们总是以中间值作为基准时)

看到这个只是想象有一半的时间我们会遇到偶数条件，这将使我们完美地分割数组，如果这种情况发生一半的次数，这意味着我们将数组分割 2 次以上比我们在一个完美的世界中会做的要多(pivot 总是将数组分成两半)。

2 * N * log(2) N = N * (log(2) N

引用:https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort