algorithm - O符号和一些数学

Question

刚开始学习算法。所以练习是找出语句是否总是/有时是真或假。嗯，我的逻辑在哪里失败了？

f(n) != O(g(n)) and g(n) != O(f(n))

O-notation0 <= f(n) <= cg(n)是c一些常数。所以这里的不相等意味着：

f(n) > cg(n) and g(n) > cf(n)

如果f(n) = g(n) = 1，让我们说c = 1/2：

1 > (1/2)*1 and 1 > (1/2)*1

所以在这种情况下是真的。但是这本书说在这种特殊情况下它是错误的。我误解了哪一部分？

Answer 1

Big-O 本身并不是0 <= f(n) <= c g(n)一些常数。存在一个数字c，使得该关系适用于“足够大”的n值。（当我们将 Big-O 称为渐近符号时，这就是我们所指的“渐近符号”，其他常见的符号是 Big-Theta 和 Big-Omega。）

例如，假设有一种算法对某些带有n元素的数据结构进行操作，并采取3n^2 + 7n + 18步骤。打电话给这个f(n)。我们说这个表达式的大 O 是O(n^2)因为存在一个常数（在这种情况下大于 3），使得对于所有“足够大”的n,值f(n) <= c n^2。