快速排序的时间复杂度nlogn是如何推导的？？

本文以快速排序为例，推导了快排的时间复杂度nlogn是如何得来的，其它算法与其类似。

对数据Data = { x1, x2... xn }：

T（n）是QuickSort（n）消耗的时间；

P（n）是Partition(n)消耗的时间；

（注：Partition专指把n个数据分为大小2份的时间）


有些文章给出了快排的精确计算结果：

C(n) = n - 1 + frac{1}{n} sum_{i=0}^{n-1} (C(i)+C(n-i-1)) = 2n ln n = 1.39n log_2 n.


【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/javawebsoa/p/3194015.html