枢轴时快速排序的时间复杂度（将列表拆分为 90%:10%）（对于均匀深度，总是最小的元素）

Question

快速排序在以下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是我们在完美世界中的两倍（枢轴总是将数组分成两半）。

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

Answer 2

谢谢@BrunoBraga 的提示。

这些是我自己的解释，我觉得比较直观易懂：

案例一：

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

由于F(N/10)是子列表的10%总是提前结束，因此我们可以将问题简化为：

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

求解这个方程得到 O(NLogN)

案例2：

因为我们知道将列表平均分成两半的最佳情况，深度为 LogN。

我们可以再次简化这个问题，使这个案例的深度大约是 LogN 的两倍。（因为 even depth 更坏的情况是列表长度只缩小 1 个元素）

因此，它的时间复杂度也是 O(NLogN)。

Time complexity of Quick Sort when pivot (split list into 90%:10%) (always smallest element for even depth)