快速排序时间复杂度证明

快排原理

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

假设选择 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)证明

Hello world!
文章已创建 209

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部