对于哪种情况 f(n) != O(g(n)) 和 g(n) != O(f(n)) 是正确的？
我对此有以下我无法理解的答案:
有时为真:对于 f(n) = 1 和 g(n) = ||n ∗ sin(n)|| 为真，而
对于任何 f(n) = O(g(n))，例如f(n) = g(n) = 1，这不是真的。
请有人帮助理解:
- 对于哪种情况有时是正确的？如果有示例解释，我们将不胜感激。
- “||”的含义是什么在这？
最佳答案
f(n) != O(g(n)) 为 true，如果对于任何给定的 k 和任何给定的 N 存在a n >= N 使得 f(n) > k*g(n)。
f(n) != O(g(n)) 和 g(n) != O(f(n)) 均成立的示例同时将是以下内容:让我们为偶数n定义f(n) = 0，为奇数定义f(n) = n n。同样，对于偶数 n 定义 g(n) = n，对于奇数 n 定义 g(n) = 0 。现在显然对于所有奇数n，无论我们选择多大的k，f(n) > kg(n) 类似地 g(n) > kf(n) 对于所有偶数 n 无论多大 <强>k是。
您的 f(n) = 1 和 g(n) = ||n ∗ sin(n)|| 示例也可以工作，因为 g(n) 正在振荡并获得任意大的 n 值 0，但也获得任意大的值，这足以满足我们对 的定义f(n) != O(g(n)) 和 g(n) != O(f(n)) 因为 f 保持不变函数1
关于algorithm - 渐进复杂性、算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52534145/