上界不必要地相交

Question

我正在学习 Big-O 符号的基础知识。

f(n) = Ω(g(n)) means c.g(n) is a lower bound on f(n) such that f(n) is always ≥ c.g(n)

f(n) = O(g(n)) means c.g(n) is an upper bound on f(n) such that f(n) is always ≤ c.g(n) for all n ≥ n0

上图上界和下界很清楚，但是为什么f(n)和上界相交？当它从上面的定义中明确时？这有意义吗？还是我只是不必要地指出？

来源：Skiena 的算法设计手册

Answer 1

根据前两个定义，应该没有交集，因为 always

f(n) = Ω(g(n)) means c.g(n) is a lower bound on f(n) such that f(n) is always ≥ c.g(n)

f(n) = O(g(n)) means c.g(n) is an upper bound on f(n) such that f(n) is always ≤ c.g(n)

这些定义并不完全正确。因为大 O 表示法的想法是在 n 非常大时检查操作数。用外行的话来说，这意味着您只有在您认为足够大的某个数字之后才开始检查复杂性。这在你的照片上有概述：

Upper and lower bounds valid for n > n0 ...

这就是为什么图片上有一条垂直线 n0。所以你不关心这一行之前的任何东西，因为你只考虑n0之后的数字足够大。

为了使这些定义完全正确，只需在它们的末尾添加 for n > n0。

Answer 2

这个定义简直不准确。 Big-O 符号是关于渐近增长的。因此，它的属性被考虑用于 "large enough N"，这意味着它可能不适用于小的 N。

在图表中，一个"large enough N"被标记为N0，之后保持限制属性。

Answer 3

除了其他答案已经说了，定义中的不等式也不正确，应该反过来：

f(n) = Ω(g(n)) means c.g(n) is a lower bound on f(n) such that f(n) is always ≥ c.g(n)

f(n) = O(g(n)) means c.g(n) is an upper bound on f(n) such that f(n) is always ≤ c.g(n)