1. 平均时间复杂度
  2. 参考

快排

algorithm

平均时间复杂度

nT(n)=[T(0)+T(n−1)+cn+T(1)+T(n−2)+cn+⋮+T(n−1)+T(0)+cn]=[T(0)+T(1)+⋯+T(n−1)]+[T(n−1)+T(n−2)+⋯+T(0)]+cn2=2[T(0)+T(1)+⋯+T(n−1)]⏟合并+cn2=2∑j=0n−1T(j)+cn2 \begin{aligned} nT(n) &= \begin{bmatrix} T(0) + T(n - 1) + cn \\ + \\ T(1) + T(n - 2) + cn \\ + \\ \vdots \\ + \\ T(n - 1) + T(0) + cn \end{bmatrix} \\ \\ &= [T(0) + T(1) + \dots + T(n-1)] + [T(n-1) + T(n-2) + \dots + T(0)] + cn^2\\ \\ &= 2\underbrace{[T(0) + T(1) + \dots + T(n-1)]}_{\text{合并}} + cn^2 \\ \\ &= 2 \sum_{j=0}^{n-1} T(j) + cn^2 \end{aligned}

根据 nT(n)可知

(n−1)T(n−1)=2∑j=0n−2T(j)+c(n−1)2(n - 1)T(n - 1) = 2 \sum_{j=0}^{n-2} T(j) + c(n - 1)^2

用 nT(n) - (n - 1)T(n - 1) 去掉求和公式

nT(n)−(n−1)T(n−1)=2∑j=0n−1T(j)+cn2−2∑j=0n−2T(j)−c(n−1)2=2T(n−1)+cn2−(cn2−2cn+c)=2T(n−1)+2cn−c\begin{aligned} nT(n) - (n - 1)T(n - 1) &= 2 \sum_{j=0}^{n-1} T(j) + cn^2 - 2 \sum_{j=0}^{n-2} T(j) - c(n - 1)^2 \\ \\ &= 2T(n - 1) + cn^2 - (cn^2 - 2cn + c) \\ \\ &= 2T(n - 1) + 2cn - c \end{aligned}

把 (n - 1)T(n - 1) 移到右侧去

nT(n)=2T(n−1)+2cn−c+(n−1)T(n−1)=[2−(n−1)]T(n−1)+2cn−c=(n+1)T(n−1)+2cn−c\begin{aligned} nT(n) &= 2T(n - 1) + 2cn - c + (n - 1)T(n - 1) \\ \\ &= [2 - (n - 1)]T(n - 1) + 2cn - c \\ \\ &=(n + 1)T(n -1) + 2cn - c \end{aligned}

把 n 移到右侧去

T(n)=(n+1)T(n−1)+2cn−cn=(n+1)T(n−1)n+2c−c1n\begin{aligned} T(n) &= \frac{(n + 1)T(n -1) + 2cn - c}{n} \\ \\ &= \frac{(n + 1)T(n -1)}{n} + 2c - c\frac{1}{n} \end{aligned}

两侧同除 n + 1

T(n)n+1=T(n−1)n+2c1n+1−c1n(n+1)T(n−1)n=T(n−2)n−1+2c1n−c1(n−1)nT(n−2)n−1=T(n−3)n−2+2c1n−1−c1(n−2)(n−1)⋮T(3)4=T(2)3+2c14−c13×4T(2)3=T(1)2+2c13−c12×3\begin{aligned} \frac{T(n)}{n + 1} &= \frac{T(n - 1)}{n} + 2c\frac{1}{n+1} - c\frac{1}{n(n + 1)} \\ \\ \frac{T(n - 1)}{n} &= \frac{T(n - 2)}{n-1} + 2c\frac{1}{n} - c\frac{1}{(n - 1)n} \\ \\ \frac{T(n - 2)}{n - 1} &= \frac{T(n - 3)}{n-2} + 2c\frac{1}{n - 1} - c\frac{1}{(n - 2)(n-1)} \\ &\vdots \\ \\ \frac{T(3)}{4} &= \frac{T(2)}{3} + 2c\frac{1}{4} - c\frac{1}{3 \times 4} \\ \\ \frac{T(2)}{3} &= \frac{T(1)}{2} + 2c\frac{1}{3} - c\frac{1}{2 \times 3} \\ \end{aligned}

将上面的公式左右相加

T(n)n+1+T(n−1)n+T(n−2)n−1+⋯+T(2)3=(T(n−1)n+T(n−2)n−1+⋯+T(2)3+T(1)2)+2c(1n+1+1n+⋯+13)−c(1n(n+1)+1(n−1)n+…12×3)=(T(n−1)n+T(n−2)n−1+⋯+T(2)3+T(1)2)+2c(1n+1+1n+⋯+13)−c(1n(n+1)+1(n−1)n+…12×3)\begin{aligned} &\frac{T(n)}{n + 1} + \frac{T(n - 1)}{n} + \frac{T(n - 2)}{n - 1} + \dots + \frac{T(2)}{3} \\ \\ =&\left (\frac{T(n - 1)}{n} + \frac{T(n - 2)}{n-1} + \dots+ \frac{T(2)}{3} + \frac{T(1)}{2} \right ) \\ &+2c \left (\frac{1}{n+1} + \frac{1}{n} + \dots + \frac{1}{3} \right ) \\ &-c \left ( \frac{1}{n(n + 1)} + \frac{1}{(n - 1)n} + \dots\frac{1}{2 \times 3} \right) \\ \\ =& \left ( \frac{T(n - 1)}{n} + \frac{T(n - 2)}{n-1} + \dots+ \frac{T(2)}{3} + \frac{T(1)}{2} \right ) \\ &+2c \left (\frac{1}{n+1} + \frac{1}{n} + \dots + \frac{1}{3} \right ) \\ &-c \left (\frac{1}{n(n + 1)} + \frac{1}{(n - 1)n} + \dots\frac{1}{2 \times 3} \right ) \\ \\ \end{aligned}

合并同类项

T(n)n+1=T(1)2+2c(1n+1+1n+⋯+13)−c(1n(n+1)+1(n−1)n+…12×3)=T(1)2+2c[(1n+⋯+13+12+1)−(1n+1+12+1)]−c[(1n(n+1)+1(n−1)n+⋯+12×3+11×2)−11×2]=T(1)2+2c[(ln⁡n+0.577+12n)−(1n+1+12+1)]−c(1−1n+1−11×2)\begin{aligned} \frac{T(n)}{n + 1} =& \frac{T(1)}{2} \\ &+2c \left (\frac{1}{n+1} + \frac{1}{n} + \dots + \frac{1}{3} \right ) \\ &-c \left (\frac{1}{n(n + 1)} + \frac{1}{(n - 1)n} + \dots\frac{1}{2 \times 3} \right ) \\ \\ =& \frac{T(1)}{2} \\ &+2c \left [ \left (\frac{1}{n} + \dots + \frac{1}{3} + \frac{1}{2} + 1 \right ) - (\frac{1}{n+1} + \frac{1}{2} + 1) \right ] \\ &-c \left [ \left (\frac{1}{n(n + 1)} + \frac{1}{(n - 1)n} + \dots + \frac{1}{2 \times 3} + \frac{1}{1 \times 2} \right ) - \frac{1}{1 \times 2} \right ] \\ \\ =& \frac{T(1)}{2} + 2c \left [\left (\ln n + 0.577 + \frac{1}{2n} \right ) - (\frac{1}{n+1} + \frac{1}{2} + 1) \right ] - c\left (1 - \frac{1}{n + 1} - \frac{1}{1 \times 2} \right ) \\ \end{aligned}

去掉常数项

T(n)n+1≈ln⁡nT(n)≈(n+1)ln⁡n≈nlog⁡n\begin{aligned} \frac{T(n)}{n + 1} &\approx \ln n \\ \\ T(n) &\approx (n + 1) \ln n \approx n \log n \end{aligned}

附录:
调和级数

1+12+13+⋯+1n=∑k=1n1n=lnk+γ+12k≈lnk+0.577+12k\begin{aligned} 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} =\sum_{k=1}^{n}\frac{1}{n} = lnk + \gamma + {\frac {1}{2k}} \approx lnk + 0.577 + \frac{1}{2k} \end{aligned}

https://zh.wikipedia.org/wiki/调和级数#发散率

11×2+12×3+⋯+1n(n+1)+1(n−1)n=(11−12)+(12−13)+⋯+(1n−1−1n)+(1n−1n+1)=1−1n+1\begin{aligned} &\frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \dots +\frac{1}{n(n + 1)} + \frac{1}{(n - 1)n} \\ \\ =& \left (\frac{1}{1} - \frac{1}{2} \right) +\left (\frac{1}{2} - \frac{1}{3} \right) + \dots + \left (\frac{1}{n - 1} - \frac{1}{n} \right) + \left (\frac{1}{n} - \frac{1}{n + 1} \right) \\ \\ =& 1 - \frac{1}{n + 1} \end{aligned}

参考

https://en.wikipedia.org/wiki/Quicksort
Quick-analysis
如何证明快速排序法的平均复杂度为 O(nlogn)？ - 知乎
https://www.quora.com/What-is-the-sum-of-the-series-1+-1-2-+-1-3-+-1-4-+-1-5-up-to-infinity-How-can-it-be-calculated