快速排序时间复杂度最好最坏
墨初 知识笔记 109阅读
快速排序复杂度最坏情况是什么？
答：快速排序复杂度最坏情况 (O (n^2))证明： 最坏情况 下就是对已经排好序的序列操作，假设是从小到大，那么last就会从 最 后一直比到first (哨兵位置) (共比较n-1次)，并且将序列分为1 和 n-1，之后n-1以类似方式被递归划分。 假设算法每次都进行了这种不对称划分，划分的 时间 代价为θ (n) [//n...
快速排序的平均时间复杂度是多少？
答：由于我们的第一个关键字是50，正好是待排序 快速排序的平均 时间复杂度 是N*logN，同时其也是实践已知的 最 快的通用排序算法，但是其 最坏 情况的 时间复杂度 依然是N的平方，但是只要我们对快速排序算法稍作修改，就可以保证其 最坏 情况的 时间复杂度 也是N*logN。 思路就是在递归达到一定深度后，将快速排序的递归调用改为堆排序，下面是我实现的代码
快速排序的时间性能取决于什么？
答：快速排序的 时间 性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。 最 好情况如图9‐9‐7所示，它是 {50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。
为什么快速排序比其他排序算法更有优势？
答：因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分割的平均。 这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。 这意味着，它比最坏情况较接近最好情况。 这个快速的平均运行时间，是快速排序比其他排序算法有实际的优势之另一个原因。 空间的消耗主要是递归造成的栈空间使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O (logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O (n)，平均情况，空间复杂度也为O (logn)。