快速排序时间复杂度

 我来答
嘟噜的电子数码
2022-11-15 · TA获得超过140个赞
知道答主
回答量:421
采纳率:0%
帮助的人:8.3万
展开全部

快速排序的平均时间复杂度和最坏时间复杂度分别是O(nlgn)、O(n^2)。

快速排序最差情况递归调用栈高度O(n),平均情况递归调用栈高度O(logn),而不管哪种情况栈的每一层处理时间都是O(n),所以,平均情况(最佳情况也是平均情况)的时间复杂度O(nlogn),最差情况的时间复杂度为O(n^2)。

评价标准:

稳定性是一个特别重要的评估标准。稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序,反之不稳定的排序算法经常会改变这个次序,这是我们不愿意看到的。

我们在使用排序算法或者选择排序算法时,更希望这个次序不会改变,更加稳定,所以排序算法的稳定性,是一个特别重要的参数衡量指标依据。就如同空间复杂度和时间复杂度一样,有时候甚至比时间复杂度、空间复杂度更重要一些。



推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式