快速排序的时间复杂度分析

ゞ浴缸里的玫瑰 2022-10-22 04:19 191阅读 0赞

# 快速排序的时间复杂度分析 #

先说结论：

最坏情况： O ( N 2 ) O(N^\{2\}) O(N2)

最好情况和平均情况： O ( N l o g N ) O(NlogN) O(NlogN)

下面开始分析。

假设一个序列共有 N 个元素，基本的快速排序的关系式是：

T ( N ) = T ( i ) + T ( N − i − 1 ) + c N T(N) = T(i) + T(N -i -1) + cN T(N)=T(i)\+T(N−i−1)\+cN

其中 i 表示一次划分后，枢纽所在的位置。对一个有 N 个元素的序列排序，其时间可以划分为 3 部分：

1）把枢纽放到合适的位置，即其左边的数都小于等于它，右边的数都大于等于它

2）对左边的部分（共有  i i i 个元素）应用快速排序

3）对右边的部分（共有  N − i − 1 N-i-1 N−i−1 个元素）应用快速排序

要想把枢纽元放到合适的位置，需要从两端向中间遍历数组，花费的时间和数组规模成正比例，设为  c N cN cN

于是就有了最上面的公式。

当子序列没有元素或者仅有 1 个元素，处理时间为常数。所以可以认为 :

T ( 0 ) = T ( 1 ) = 1 T(0) = T(1)=1 T(0)=T(1)=1

## 最坏情况 ##

枢纽始终是最小元素。此时  i = 0 i = 0 i=0，那么递推关系是：

T ( N ) = T ( 0 ) + T ( N − 1 ) + c N , T(N) = T(0) + T(N -1) + cN , T(N)=T(0)\+T(N−1)\+cN,  ( N > 1 ) (N>1) (N>1)

忽略掉  T ( 0 ) = 1 T(0)=1 T(0)=1 这样的常数项，上面的式子就是：

T ( N ) = T ( N − 1 ) + c N T(N) = T(N -1) + cN T(N)=T(N−1)\+cN (1)

反复使用上面的式子，得到

T ( N − 1 ) = T ( N − 2 ) + c ( N − 1 ) T(N-1) = T(N -2) + c(N-1) T(N−1)=T(N−2)\+c(N−1) (2)

T ( N − 2 ) = T ( N − 3 ) + c ( N − 2 ) T(N-2) = T(N -3) + c(N-2) T(N−2)=T(N−3)\+c(N−2) (3)

…

最后把  N = 2 N=2 N=2 带入:

T ( 2 ) = T ( 1 ) + c ( 2 ) T(2) = T(1) + c(2) T(2)=T(1)\+c(2) (4)

把从 （1） 到 （4）还有省略号，这些式子加起来，消除共同的项，得到：

T ( N ) = T ( 1 ) + c ∑ i = 2 N i = O ( N 2 ) T(N) = T(1) + c\\sum\_\{i=2\}^\{N\} i=O(N^\{2\}) T(N)=T(1)\+ci=2∑Ni=O(N2)

## 最好情况 ##

最幸运的是，枢纽恰好位于序列的中间。

为了方便分析，假设数组有奇数个元素， N = 2 n + 1 , ( n > = 1 ) N = 2n+1,(n>=1) N=2n\+1,(n>=1)

所以有

T ( N ) = T ( n ) + T ( n ) + c N , T(N) = T(n) + T(n) + cN , T(N)=T(n)\+T(n)\+cN,  ( N > 1 ) (N>1) (N>1)

因为  n = N − 1 2 n = \\frac\{N-1\}\{2\} n=2N−1，忽略到无关紧要的常数，再简化一下， n = N 2 n = \\frac\{N\}\{2\} n=2N，代入上式

T ( N ) = T ( N / 2 ) + T ( N / 2 ) + c N , T(N) = T(N/2) + T(N/2) + cN , T(N)=T(N/2)\+T(N/2)\+cN,  ( N > 1 ) (N>1) (N>1)

也就是

T ( N ) = 2 T ( N / 2 ) + c N , T(N) = 2T(N/2) + cN , T(N)=2T(N/2)\+cN,  ( N > 1 ) (N>1) (N>1)

两边同时除以  N N N

T ( N ) N = T ( N / 2 ) N / 2 + c \\frac\{T(N)\}\{N\} =\\frac\{T(N/2)\}\{N/2\} + c NT(N)=N/2T(N/2)\+c （1）

反复套用这个式子

T ( N / 2 ) N / 2 = T ( N / 4 ) N / 4 + c \\frac\{T(N/2)\}\{N/2\} =\\frac\{T(N/4)\}\{N/4\} + c N/2T(N/2)=N/4T(N/4)\+c （2）

T ( N / 4 ) N / 4 = T ( N / 8 ) N / 8 + c \\frac\{T(N/4)\}\{N/4\} =\\frac\{T(N/8)\}\{N/8\} + c N/4T(N/4)=N/8T(N/8)\+c （3）

…

最后把  N = 2 N=2 N=2 带入

T ( 2 ) 2 = T ( 1 ) 1 + c \\frac\{T(2)\}\{2\} =\\frac\{T(1)\}\{1\} + c 2T(2)=1T(1)\+c （4）

把从 （1） 到 （4）还有省略号，这些式子加起来，消除共同的项，得到：

T ( N ) N = T ( 1 ) 1 + c x \\frac\{T(N)\}\{N\} =\\frac\{T(1)\}\{1\} + cx NT(N)=1T(1)\+cx （5）

x x x 表示这些式子有多少个，我们算一下

其个数就是等比数列 `2,4,8,16,32,…,N` 的个数

根据等比数列的通项公式  a n = a 1 q n − 1 a\_\{n\} = a\_\{1\}q^\{n-1\} an=a1qn−1

带入  a 1 = 2 , a n = N ， q = 2 a\_\{1\} =2 , a\_\{n\} = N， q=2 a1=2,an=N，q=2 得到

N = 2 n N =2^\{n\} N=2n

所以  n = log ⁡ 2 N n = \\log\_\{2\}N n=log2N

所以式子（5）是

T ( N ) N = T ( 1 ) 1 + c log ⁡ 2 N \\frac\{T(N)\}\{N\} =\\frac\{T(1)\}\{1\} + c\\log\_\{2\}N NT(N)=1T(1)\+clog2N （6）

由此得到

T ( N ) = N + c N log ⁡ 2 N T(N) = N + cN\\log\_\{2\}N T(N)=N\+cNlog2N

忽略系数  c c c 和低阶项  N N N，得到

T ( N ) = O ( N l o g N ) T(N) = O(NlogN) T(N)=O(NlogN)

## 平均情况 ##

这是最难的部分。

T ( N ) = T ( i ) + T ( N − i − 1 ) + c N T(N) = T(i) + T(N -i -1) + cN T(N)=T(i)\+T(N−i−1)\+cN （1）

依然从上面的递推关系式入手。

对于平均情况，很难说每一次划分枢纽元会出现在哪里，也许出现在第  0 0 0 个位置，也许出现在第  （ N − 1 ） （N-1） （N−1）个位置，但是平均来说，每个位置出现的概率相等，都是  N / 1 N/1 N/1

所以上式的  T ( i ) T(i) T(i) 要换成  ( 1 / N ) ∑ i = 0 N − 1 T ( i ) (1/N)\\sum\_\{i=0\}^\{N-1\}T(i) (1/N)∑i=0N−1T(i)

同理， T ( N − i − 1 ) T(N -i -1) T(N−i−1) 也可以换成  ( 1 / N ) ∑ i = 0 N − 1 T ( i ) (1/N)\\sum\_\{i=0\}^\{N-1\}T(i) (1/N)∑i=0N−1T(i)

于是（1）变为

T ( N ) = ( 2 / N ) \[ ∑ i = 0 N − 1 T ( i ) \] + c N ， N > = 2 T(N) = (2/N)\[\\sum\_\{i=0\}^\{N-1\}T(i)\]+ cN ， N>=2 T(N)=(2/N)\[i=0∑N−1T(i)\]\+cN，N>=2 （2）

两边同时乘以 N

N T ( N ) = 2 \[ ∑ i = 0 N − 1 T ( i ) \] + c N 2 NT(N) = 2\[\\sum\_\{i=0\}^\{N-1\}T(i)\]+ cN^2 NT(N)=2\[i=0∑N−1T(i)\]\+cN2 （3）

用  N − 1 N-1 N−1 来替换  N N N

( N − 1 ) T ( N − 1 ) = 2 \[ ∑ i = 0 N − 2 T ( i ) \] + c ( N − 1 ) 2 (N-1)T(N-1) = 2\[\\sum\_\{i=0\}^\{N-2\}T(i)\]+ c(N-1)^2 (N−1)T(N−1)=2\[i=0∑N−2T(i)\]\+c(N−1)2 （4）

(3) 减去（4） 得到

N T ( N ) − ( N − 1 ) T ( N − 1 ) = 2 T ( N − 1 ) + 2 c N − c NT(N) -(N-1)T(N-1) = 2T(N-1)+2cN-c NT(N)−(N−1)T(N−1)=2T(N−1)\+2cN−c （5）

移项

N T ( N ) = ( 2 + N − 1 ) T ( N − 1 ) + 2 c N − c NT(N) = (2+N-1)T(N-1)+2cN-c NT(N)=(2\+N−1)T(N−1)\+2cN−c （6）

化简，并忽略常数 c

N T ( N ) = ( N + 1 ) T ( N − 1 ) + 2 c N NT(N) = (N+1)T(N-1)+2cN NT(N)=(N\+1)T(N−1)\+2cN （7）

两边同时除以  N ( N + 1 ) N(N+1) N(N\+1)

T ( N ) N + 1 = T ( N − 1 ) N + 2 c N + 1 \\frac\{T(N)\}\{N+1\} =\\frac\{T(N-1)\}\{N\} + \\frac\{2c\}\{N+1\} N\+1T(N)=NT(N−1)\+N\+12c （8） 现在可以进行叠缩，不断套用式子（8）

T ( N − 1 ) N = T ( N − 2 ) N − 1 + 2 c N \\frac\{T(N-1)\}\{N\} =\\frac\{T(N-2)\}\{N-1\} + \\frac\{2c\}\{N\} NT(N−1)=N−1T(N−2)\+N2c （9）

T ( N − 2 ) N − 1 = T ( N − 3 ) N − 2 + 2 c N − 1 \\frac\{T(N-2)\}\{N-1\} =\\frac\{T(N-3)\}\{N-2\} + \\frac\{2c\}\{N-1\} N−1T(N−2)=N−2T(N−3)\+N−12c （10）

…

把  N = 2 N=2 N=2 带入 （8）

T ( 2 ) 3 = T ( 1 ) 2 + 2 c 3 \\frac\{T(2)\}\{3\} =\\frac\{T(1)\}\{2\} + \\frac\{2c\}\{3\} 3T(2)=2T(1)\+32c （11）

把 (8，9，10，11) 和省略号的式子加起来

T ( N ) N + 1 = T ( 1 ) 2 + 2 c ∑ i = 3 N + 1 ( 1 / i ) \\frac\{T(N)\}\{N+1\} =\\frac\{T(1)\}\{2\} + 2c\\sum\_\{i=3\}^\{N+1\}(1/i) N\+1T(N)=2T(1)\+2ci=3∑N\+1(1/i) （12）

忽略常数  T ( 1 ) 2 \\frac\{T(1)\}\{2\} 2T(1) 和系数 2c，我们研究一下  ∑ i = 3 N + 1 ( 1 / i ) \\sum\_\{i=3\}^\{N+1\}(1/i) ∑i=3N\+1(1/i)

这个式子就是

1 3 + 1 4 + 1 5 + . . . + 1 N + 1 \\frac\{1\}\{3\} + \\frac\{1\}\{4\} + \\frac\{1\}\{5\}+...+\\frac\{1\}\{N+1\} 31\+41\+51\+...\+N\+11 (13)

当 n 很大时

1 + 1 2 + 1 3 + . . . + 1 n = l n ( n ) + γ 1 + \\frac\{1\}\{2\} + \\frac\{1\}\{3\} + ...+\\frac\{1\}\{n\} = ln(n)+ \\gamma 1\+21\+31\+...\+n1=ln(n)\+γ (14)

其中的  γ \\gamma γ 是欧拉常数，近似值是 0.57721566490153286060651209，目前还不知道它是有理数还是无理数。

对比（14）和（13），当（13）中的  N N N 很大时，它的和近似等于

l n ( N + 1 ) + γ − 3 / 2 ln(N+1)+ \\gamma - 3/2 ln(N\+1)\+γ−3/2

结合式子 （12）得出：

T ( N ) N + 1 = O ( l o g N ) \\frac\{T(N)\}\{N+1\} = O(logN) N\+1T(N)=O(logN) （12）

从而，

T ( N ) = O ( N l o g N ) T(N) = O(NlogN) T(N)=O(NlogN)

--------------------

参考资料：

《数据结构与算法分析——C语言描述》（机械工业出版社）