为什么集合中的Big Theta是Big O，而不是相同函数的Big Theta？

Question

我正在通读我的算法文本，它说：

​

​

但是，反之亦然，只要函数g(n)在两种情况下是相同的，反之亦然？

我理解为什么它不适用于不同的函数，即n^2和n。但是对于同一函数，不能使用任意大小的常量来包围O(g(n))，使其渐近紧凑吗？

Answer 1

反之亦然，因为O符号为函数的复杂度建立了一个上限，而Theta则同时建立了一个上限和下限。

例如，对于f(x) = x²，你可以说f(x) = O(x³)，因为x³确实是x²的上界，但你不能说f(x) = ϴ(x³)，因为x³不是x²的下界。

Take a look here for the precise definitions of O and ϴ notations