o应该取哪一种说法？

来源：2-1 究竟什么是大O（Big O）

weixin_慕仔4424139

2020-03-01

课件里先说o是算法执行的最低上界，之后又说它指的是平均情况。请问这两种说法是矛盾的吗？分析复杂度时应该按哪种说法来取？谢谢老师！

写回答

1回答

liuyubobobo

2020-03-01

严格的数学定义，大 O 是指上界，即最坏的情况。

只有在算法是随机算法的时候，我们通常说的是时间复杂度的期望。但在此时，严谨说要加上说明，即该算法的的时间复杂度期望是什么什么；

另外，在均摊复杂度分析上，我们有的时候说的是平均情况。但在此时，也要加上说明，即该算法的均摊分析时间复杂度是什么什么。

如果没有特殊说明，按照严格的数学定义，大 O 是指上界，即最坏的情况。

继续加油！：）

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 2

回答 1