快速排序最好情况下的时间复杂度
终极管理员 知识笔记 86阅读
快速排序复杂度最坏情况是什么？
答：快速排序复杂度最坏情况 (O (n^2))证明： 最坏情况 下就是对已经排好序的序列操作，假设是从小到大，那么last就会从 最 后一直比到first (哨兵位置) (共比较n-1次)，并且将序列分为1 和 n-1，之后n-1以类似方式被递归划分。 假设算法每次都进行了这种不对称划分，划分的 时间 代价为θ (n) [//n...
如何计算快速排序时间复杂度？
答：快速排序最优的情况就是每一次取到的元素都刚好平分整个数组。 此时的时间复杂度公式则为：T [n] = 2T [n/2] + f (n)；T [n/2]为平分后的子数组的时间复杂度，f [n] 为平分这个数组时所花的时间；下面来推算下，在最优的情况下快速排序时间复杂度的计算 (用迭代法)： 当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T [1]时，说明这个公式已经迭代完了（T [1]是常量了）。 快速排序 在C++的泛型 排序 中，拷贝对象需要很大的开销，而比较对象常常是相对省时的（编译器的自动优化）。 在这种情况下，如果我们能够使用更少的数据移动，那么有理由让一个 算法 多使用一些比较。
快速排序法的性能是什么？
答：我们来分析一下快速排序法的性能。 快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。 如图所示，它是 {50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。
为什么快速排序比其他排序算法更有优势？
答：因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分割的平均。 这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。 这意味着，它比最坏情况较接近最好情况。 这个快速的平均运行时间，是快速排序比其他排序算法有实际的优势之另一个原因。 空间的消耗主要是递归造成的栈空间使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O (logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O (n)，平均情况，空间复杂度也为O (logn)。