f(n)= O(g(n))或g(n)= O(f(n))

Question

我试图证明这对于任何具有域和共域N的函数f和g是正确的.我已经看到它使用限制证明了它,但显然你也可以在没有它们的情况下证明它.

基本上我要证明的是"如果f(n)没有g(n)的大O,那么g(n)必须有f(n)的大O.我有什么麻烦是试图理解"f没有大的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)).这并不能证明ac'存在于g(n)<= c'f(n),这将成功地证明这个问题.

Answer 1

首先,你对big-O的定义有点偏僻.你说:

我认为这意味着没有c能够满足n的所有值的这种不等式.

实际上,您需要选择一个值c来满足任何值的不等式n.

无论如何,要回答这个问题:

我不相信问题中的陈述是真的......让我们看看我们是否可以想到一个反例,其中f(n)≠O(g(n))和g(n)≠O(f( N)).

注意:我将使用n并x互换,因为我更容易这样思考.

我们必须提出两个功能,当它们走向无限时,它们会不断地相互交叉.不仅如此,他们还必须继续相互交叉,不管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大于N,使得f(x) = x^2和g(x) = x.同样,会有x2这样的g(x) = x^2和f(x) = x.

在这些点上,您将无法选择任何c1或c2那些将确保那个f(x) < c1 * g(x)或那个g(x) < c2 * f(x).

总之,f(n)≠O(g(n))并不意味着g(n)= O(f(n)).

Answer 2

不对。设f(n) = 1if n为奇数，否则为零，g(n) = 1if 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)是不可能的。因此，f是O(g)不是真的。

同样，我们可以证明g是O(f)不正确的。