O-notation和一些数学

Question

刚开始学习算法。因此，练习是要查明陈述是否总是/有时是真或假。 Em，我的逻辑在哪里失败？

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

O形表示法是0 <= 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)。我们说这个表达式的Big-O是O(n^2)，因为存在一个常量（在这个例子中大于3），这样对于所有“足够大”的值n,f(n) <= c n^2。