快速排序时间复杂度分析（递归方程分析）

Question

Quicksort的重复方程是

T(n) = T(n/2) + T(n/2) + theta(n)

如果数据透视始终将原始数组分为两个相同大小的子数组。

所以总的时间复杂度为O（nlogn）

但是如果两个子列表的比率始终为1:99怎么办？

等式肯定是T(n) = T(n/100) + T(99n/100) + theta(n)

但是如何从上述方程式得出时间复杂度？

我读过其他答案，它描述了我们可以忽略T（n / 100），因为T（99n / 100）将主导整个时间复杂度。

但是我完全不能完全理解。

任何建议将不胜感激！

Answer 1

插入T(n) = n log(n) + Θ(n)，您得到

n log(n) + Θ(n) = n/100 log(n/100) + 99n/100 log(99n/100) + Θ(n/100) + Θ(99n/100) + Θ(n)
                = n log(n)/100 + 99n log(n)/100 - n/100 log(100) - 99n/100 log(99/100) + Θ(n)
                = n log(n) + Θ(n)

实际上任何分数都将起作用：

T(n) = T(pn) + T((1-p)n) + Θ(n)

由O(n log(n))解决。