时间戳

首页 > 解决方案 > 快速排序时间复杂度分析（递归方程分析）

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

问题描述

快速排序的递推方程为

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

如果 pivot 总是将原始数组分成两个相同大小的子数组。

所以整体时间复杂度为 O(nlogn)

但是如果两个子列表的比例总是1:99呢？

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

但是我怎样才能从上面的等式中推导出时间复杂度呢？

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

但我完全不能完全理解。

任何意见，将不胜感激！

标签： time-complexity

解决方案

插头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))。

推荐阅读