1回答

liuyubobobo

2021-04-23

因为大 O 描述的是上界，这个上界不一定是最紧的上界。

大 O 的严格数学定义如下（来自算法导论）：

对于 2n + 8，我们显然可以找到一个 c 和 n0，满足当 n >= n0 时， cn^2 >= 2n + 8。

但是，通常，我们在交流的时候，对大 O 的使用，都会去说那个最紧的上界。

所以，在面试的时候，不要说一个线性算法的复杂度是 O(n^2)，虽然从大 O 的数学定义的角度，这是对的。

继续加油！：）

1

0