描述一个算法复杂度应该是说最坏情况还是平均情况

Question

老师您好，我听过您的算法体系课程，在那个课程中，我记得您说过，通常说一个算法的复杂度都是指它的最坏情况下的复杂度（除了随机算法等特殊情况以外），但是在这个课程中，您说一个算法的复杂度是指一般情况也就是平均情况的复杂度。我感觉还想有点疑惑，到底该以哪个为准呢？

Answer 1

liuyubobobo 2020-11-27 14:44:31

我在这个课程的哪里说过这句话？我看一下上下文？

• 提问者 weixin_慕慕4340848 #1

  老师您看一下2-1节，18分钟。

• liuyubobobo 回复 提问者 weixin_慕慕4340848 #2

  嗯，明白了。在大多数情况下，平均情况和最坏情况是一样的。但是对于快速排序这样的算法，因为最坏是 O(n^2)，平均是 O(nlogn)，我们一般取 O(nlogn)。所以在这个课程中，我统一说成了取平均情况。在算法体系课成中，我讲的更细一些，把快速排序这种随机化算法单独看待，这类随机化算法要看平均情况，其他算法看最坏情况；在一些累计调用的过程或者特殊的时候要看均摊。其实重点是：我们不能看最好情况：）

• 提问者 weixin_慕慕4340848 回复 liuyubobobo #3

  好的，谢谢老师。我想再问一下，咱们平时说的大O实际上严格来说应该是Θ这个符号对吗？

点开查看后面2条评论