时间复杂度

来源：3-6 随机化快速排序法

慕斯9050251

2018-05-03

老师您好，我想问一下在排序章节中，时间复杂度O(n^2),nlog(n)考虑的都是什么情况下的，是平均情况还是最坏情况，平均情况的话是怎么计算得到的呀？

写回答

1回答

liuyubobobo

2018-05-03

除了快速排序，考虑的都是最坏情况。快速排序考虑的是平均情况。

选择排序和插入排序最坏O(n^2)的复杂度应该无需多言了：）

归并排序最坏是O(nlogn)的复杂度，其中的分析在视频课程的3-1有介绍，也可以参考以下问答：

快速排序在加入随机化以后，复杂度分析比较困难。首先，理论上快排的最差复杂度是O(n^2)的，即每次随机的标定点都在当前待排序数组的一端。但实际上，发生这种情况的概率的非常低，n越大，概率越低。这个课程带领大家进行了实测，一旦快排加入了随机化，对于任何情况，都是可以在很快的速度下完成排序的。

具体的复杂度分析，实际上要引入概率论中期望的概念，即假设每次在待排序数组中随机到任意元素作为标定点的概率是相等的，求出最终快排复杂度的期望。如果对这个严格的数学过程感兴趣，可以参考《算法导论》中快排相关的章节，有严格的数学推导过程。

不过如果不想看严格的数学推导，只是想进行直观的理解，可以参考这里：https://coding.imooc.com/learn/questiondetail/15858.html

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11186 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1