快速排序的空间复杂度是多少

2021.02.27 15:02 439
阅读约 2 分钟

快速排序的空间复杂度是多少?
主要是递归造成的栈空间的使用,最好情况,递归树的深度为 log2​n

空间复杂度也就为 O(logn)

最坏情况,

需要进行n‐1递归调用,其空间复杂度为O(n),

平均情况,

空间复杂度也为O(logn)。

时间复杂度的最好最坏的情况是多少,有哪些优化方案?
在最优的情况下

快速排序算法的时间复杂度为O(nlogn)。

最坏的情况,

待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。如果递归树画出来,它就是一棵斜树。

此时需要执行n‐1次递归调用,且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录,也就是枢轴的位置,因此比较次数为

 

最终其时间复杂度为O(n^2)。

时间复杂度优化:
使用三者取中的方法可以有效降低最坏情况下的时间复杂度。
三者取中的意思,就是将枢轴的值设置为 A[low] 、A[(low + high)/2] 、A[high] 中的中间值。
 

字数:409 发布于 7 个月前
Copyright 2018-2021 Siques