我试图证明这对于任何具有域和共域 N 的函数 f 和 g 都是正确的。我已经看到它使用限制来证明，但显然你也可以在没有它们的情况下证明它。
基本上我要证明的是“如果 f(n) 没有 g(n) 的大 O，那么 g(n) 必须有 f(n) 的大 O。我所拥有的麻烦是试图理解“f没有g的大O”是什么意思。
根据 big-O 的正式定义，如果 f(n) = O(g(n)) 那么 n>=N -> f(n) <= cg(n) 对于一些 N 和一个常数 c。如果 f(n) != O(g(n)) 我认为这意味着没有 c 可以满足所有 n 值的不等式。然而我看不出我能做些什么来使用这个事实来证明 g(n) = O(f(n))。这并不能证明 g(n) <= c'f(n) 存在 c'，这将成功地证明这个问题。
不对。f(n) = 1如果是奇数n，否则为零，g(n) = 1如果n是偶数，否则为零。
说那f是O(g)说有一个常数C > 0，N > 0这n > N意味着f(n) <= C g(n)。让n = 2 * N + 1，所以这n很奇怪。那么f(n) = 1，g(n) = 0那f(n) <= C * g(n)是不可能的。因此，fisO(g)不正确。
同样，我们可以证明这g不是O(f)真的。
首先，您对 big-O 的定义有点偏离。你说：
我认为这意味着没有 c 可以满足所有 n 值的不等式。
实际上，您需要为 的任何c值选择一个满足不等式的值。n
我不相信问题中的陈述是真的......让我们看看我们是否可以想到一个反例，其中 f(n) ≠ O(g(n)) 和 g(n) ≠ O(f( n))。
注意：我将使用nandx互换，因为这样想更容易。
我们必须想出两个函数，当它们走向无穷大时，它们会不断地相互交叉。不仅如此，它们还必须继续相互交叉，而不管c我们将它们乘以的常数如何。
所以这让我认为这些函数必须在两个不同的时间复杂度之间交替。
让我们看一个在y = x和之间交替的函数y = x^2：
f(x) = .2 (x * sin(x) + x^2 * (1 - sin(x)) )
现在，如果我们创建一个带有轻微偏移振荡的类似函数：
g(x) = .2 (x * cos(x) + x^2 * (1 - cos(x)) )
然后这两个函数将继续相互交叉，直到无穷大。
对于您选择的任何数字N，无论多高，都会有一个x1大于和。同样，会有这样的和。Nf(x) = x^2g(x) = xx2g(x) = x^2f(x) = x
此时，您将无法选择任何c1or c2that 将确保 that f(x) < c1 * g(x)or that g(x) < c2 * f(x)。
总之，f(n) ≠ O(g(n)) 并不意味着 g(n) = O(f(n))。