快速排序时间复杂度为O（n×log（n））的证明
2024-04-04 21:30:11
快速排序时间复杂度为O（n×log（n））的证明
之前只知道快速排序的平均时间复杂度为O（n×log（n）），最糟糕时复杂度为O（n^2），但却不知道具体原因，今天好好证明一下，最后部分摘自《算法导论》。
首先再介绍一遍快排的思想：
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
1、最优情况
在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为 [log2n]+1（ [x] 表示不大于 x 的最大整数），即仅需递归 log2n 次，需要时间为T（n）的话，第一次Partiation应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。于是不断地划分下去，就有了下面的不等式推断：
这说明，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。
2、最糟糕情况
然后再来看最糟糕情况下的快排，当待排序的序列为正序或逆序排列时，且每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为
，最终其时间复杂度为O(n^2)。
3、一般情况
最后来看一下一般情况，平均的情况，设枢轴的关键字应该在第k的位置（1≤k≤n），那么：
本来想按这种思路推导出来，结果发现半天推不出结果，最后去翻阅《算法导论》7.4节，发现证明过程还是蛮复杂的，我就偷懒贴一下好了~
最新文章
- ABP理论学习之应用服务
- 阿里云服务器远程mysql连不上
- C#小程序呢飞行棋设计分析
- selenium webdriver学习（一）
- m3u8字段意义解析
- Sonatype Nexus高级配置
- 【转】10.4新特性-ArcGIS 10.4矢量切片介绍
- SVN与TortoiseSVN实战：从入门到精通
- 【vijos1642】班长的任务
- HDU 2087 剪花布条 KMP
- angular控制器、服务和指令三者之间的关系
- 记一次 net 使用 data.oracleclient 使用错误OCIEnvCreate 失败, 返回代码为-1
- json转数组
- 深度学习课程笔记（十一）初探 Capsule Network
- 移动端 input 输入框实现自带键盘“搜索“功能并修改X
- Android开发教程 - 使用Data Binding（六）RecyclerView Adapter中的使用
- j.u.c系列（10）---之并发工具类：Semaphore
- MTK 预置apk
- Python yield详解***
- [翻译] LazyFadeInView 渐入显示text文本