快速排序的最优时间复杂度是 \(O(nlogn)\)，最差时间复杂度是 \(O(n^2)\)，期望时间复杂度是 \(O(nlogn)\)。
这里我们证明一下快排的期望时间复杂度。
设 \(T(n)\) 为对长度为 \(n\) 的序列进行快速排序所需要的期望时间。我们有：
\[T(0) = 0\]
以及： \[T(n) = n + \frac{1}{n}\sum_{i=0}^{n-1}(T(i) + T(n - i - 1))\]
我们可以通过放缩来获得对 \(T(n)\) 上界的一个估计。
\[T(n) = n + \frac{1}{n}\sum_{i=0}^{n-1}(T(i) + T(n - i - 1))\]\[ = n + \frac{2}{n}\sum_{i=\frac{2}{n}}^{n-1}(T(i) + T(n - i - 1))\]\[ = n + \frac{2}{n}\sum_{i=\frac{2}{n}}^{\frac{3n}{4}}(T(i) + T(n - i - 1)) + \frac{2}{n}\sum_{i=\frac{3n}{4}}^{n-1}(T(i) + T(n - i - 1)) \]
因为 \(T(n) >= n\) , 所以对于 \(\frac{n}{2} <= i <= j\)，我们显然有：
\[T(i) + T(n - i) <= T(j) + T(n - j)\]
所以：
\[T(n) <= n + \frac{2}{n}\sum_{i=\frac{2}{n}}^{\frac{3n}{4}}(T(\frac{3n}{4}) + T(\frac{n}{4})) + \frac{2}{n}\sum_{i=\frac{3n}{4}}^{n-1}(T(n - 1) + T(0))\]\[<= n + \frac{1}{2}(T(\frac{3n}{4}) + T(\frac{n}{4})) + \frac{1}{2}T(n-1) \]
我们要证明 \(T(n) = O(nlogn)\) , 这需要证明存在常数 \(c\) 满足 \(T(n) <= cnlogn\)。
我们考虑用数学归纳法证明。\(n = 0\)时定理显然成立。现在假设对于 \(m <= n\) 定理皆成立。那么：
\[T(n) <= n + \frac{1}{2}(T(\frac{3n}{4}) + T(\frac{n}{4})) + \frac{1}{2}T(n-1) \]
\[<= n +\frac{1}{2}(c(\frac{3n}{4})log(\frac{3n}{4}) + c(\frac{n}{4})log(\frac{n}{4})) + \frac{1}{2}c(n-1)log(n-1)\]
\[<= n +c(\frac{3n}{8}log(n) - \frac{3n}{8}log(\frac{4}{3}) + \frac{n}{8}log(n) - \frac{n}{8}log(4) + \frac{n}{2}log(n))\]
\[= cnlogn + n(1 - \frac{3c}{8}log(\frac{4}{3}) - \frac{c}{4})\]
当 \(1 - \frac{3c}{8}log(\frac{4}{3}) - \frac{c}{4} <= 0\) 时，也即约 \(c >= \frac{5}{2}\)，我们有：
\[T(n) <= cnlogn\].
归纳成立，\(T(n) = O(nlogn)\).
转载于:https://www.cnblogs.com/LzyRapx/p/9565827.html
