证明f(n)=Θg(g(n))敌我识别(n)=Θ(f(n))

I have been given the problem:

我遇到了这样的问题:

f(n) are asymptotically positive functions. Prove f(n) = Θ(g(n)) iff g(n) = Θ(f(n)).

Everything I have found points to this statement being invalid. For example an answer I've come across states:

我所发现的一切都表明这个声明是无效的。例如，我遇到的一个答案是:

f(n) = O(g(n)) implies g(n) = O(f(n))
f(n) = O(g(n)) means g(n) grows faster than f(n). It cannot imply that f(n) grows
faster than g(n). Hence not true.

Another states:

另一个州:

 If f(n) = O(g(n)) then O(f(n)). This is false. If f(n) = 1 and g(n) = n 
 for all natural numbers n, then f(n) <= g(n) for all natural numbers n, so
 f(n) = O(g(n)). However, suppose g(n) = O(f(n)). Then there are natural
 numbers n0 and a constant c > 0 such that n=g(n) <= cf(n) = c for all n >= 
 n0 which is impossible.

I understand that there are slight differences between my exact question and the examples I have found, but I've only been able to come up with solutions that do not prove it. I am correct in thinking that it is not able to be proved or am I looking over some detail?

我知道我的确切问题和我找到的例子之间存在细微的差别，但我只能想出一些无法证明它的解决方案。我的想法是正确的，它是不能被证明的，还是我在寻找一些细节?

1 个解决方案

#1

You can start from here:

你可以从这里开始:

Formal Definition: f(n) = Θ (g(n)) means there are positive constants c1, c2, and k, such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k.

正式定义:f(n)=Θ(g(n))意味着有积极的c1,c2,和k,这样0≤c1g f(n)(n)≤≤c2g所有n≥k(n)。

Because you have that iff, you need to start from the left side and to prove the right side, and then start from the right side and prove the left side.

因为你有iff，你需要从左边开始证明右边，然后从右边开始证明左边。

Left -> right

左- >右

We consider that:

我们认为:

f(n) = Θ(g(n))

and we want to prove that

我们想证明这一点。

g(n) = Θ(f(n))

So, we have some positive constants c1, c2 and k such that:

所以，我们有一些正的常数c, c和k

0 ≤ c1*g(n) ≤ f(n) ≤ c2*g(n), for all n ≥ k

The first relation between f and g is:

f和g的第一个关系是:

c1*g(n) ≤ f(n)     =>     g(n) ≤ 1/c1*f(n)    (1)

The second relation between f and g is:

f和g的第二个关系是:

f(n) ≤ c2*g(n)     =>     1/c2*f(n) ≤ g(n)    (2)

If we combine (1) and (2), we obtain:

如果我们合并(1)和(2)，我们得到:

1/c2*f(n) ≤ g(n) ≤ 1/c1*f(n)

If you consider c3 = 1/c2 and c4 = 1/c1, they exist and are positive (because the denominators are positive). And this is true for all n ≥ k (where k can be the same).

如果你考虑c3 = 1/c2和c4 = 1/c1，它们存在并且是正的(因为分母是正的)。这是适用于所有n≥k(k可以是相同的)。

So, we have some positive constants c3, c4, k such that:

所以我们有一些正的常数c3 c4 k这样的

c3*f(n) ≤ g(n) ≤ c4*f(n), for all n ≥ k

which means that g(n) = Θ(f(n)).

这意味着g(n)=Θ(f(n))。

Analogous for right -> left.

类似于右边->左边。

#1