快速排序时间复杂度证明

快排原理

快排, 最好理解的说法为: 选择数组中任意一个数字, 将比其小的数替换到左边, 比其大的数放在右边, 之后重复上述操作. 这里选择的数字直接决定算法的时间复杂度.

假设选择 56 作为比较数字, 然后执行上述操作:

1. 原数组, 从第一个数字开始遍历, 和 56 比较
   46 30 82 90 56 17 95 15

2. 遇见第一个数字 46, 比 56 小, 记录比 56 小的节点位置(1, 粗体),
   46 30 82 90 56 17 95 15

3. 继续往后遍历, 30, 比 56 小, 顺移比 56 小的位置,
   46 30 82 90 56 17 95 15

4. 继续往后遍历, 82, 比 56 大, 不执行操作, 继续遍历, 直到遇见比 56 小的数
   46 30 82 90 56 17 95 15

5. 17, 比 56 小, 将 17 替换到最后一个粗体之后,
   46 30 82 90 56 17 95 15
   46 30 15 90 56 17 95 82

6. 继续遍历, 发现没有比 56 小的数了, 将 56 移动到最后一个黑体数字之后
   46 30 15 90 56 17 95 82
   46 30 15 56 90 17 95 82

7. 第一遍遍历结束

时间复杂度

定义待排序数组长度 n, 定义快速排序函数方程为 f(n)

理想状态下, 执行第一遍排序之后, 结果为:

$$f(n) = 2f(n/2) + n$$

第二遍为:

$$f(n) = 4f(n/4) + 2n$$

第三遍为:

$$f(n) = 8f(n/8) + 3n$$

递推可得第 k 遍:

$$ f(n) = 2^kf(\frac {n}{2^k}) + kn$$

最后必为

$$ f(\frac {n}{2^k}) = f(1)$$

$$即\quad \frac {n}{2^k} = 1, \log_2n = k$$

$$\quad f(n) = nf(1) + n\log_2n \quad O(n\log_2n)$$

更多

上述的时间复杂度是建立在一切完美的情况下的, 一般证明方法移步: 快速排序的期望复杂度O(nlogn)证明