刚开始学习算法。因此，练习是找出语句是否始终/有时为真或为假。 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
所以在这种情况下是正确的。但是这本书说在这个特殊情况下这是错误的。我误解了哪一部分？
最佳答案
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 .
关于algorithm - O 符号和一些数学，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11130910/