渐近符号属性证明？

Question

我试图证明如果 f(n) 和 g(n) 是渐近正函数，那么：

1. f(n) = O((f(n))^2)

2. f(n) = O(g(n)) 意味着 2^(f(n)) = O(2^(g(n)))

3. f(n) = O(g(n)) 意味着 g(n) = O(f(n))

Answer 1

1）定理：如果f(n)是渐近正函数从自然数到自然数，则f(n) = O((f(n)) ^2)（注意我添加了一个额外的，可能是隐含的假设）。

证明：因为f(n)是自然数到自然数的渐近正函数，所以保证对于所有大于等于某个自然数n0的自然数n，f(n)>0，因此 f(n) >= 1。因为 f(n) 保证为正，我们可以自由地将不等式两边乘以 f(n)，而不改变方向得到 f(n)^​​2 >= f( n).因此，我们可以选择 c = 1 并使用假设中的 n0 来证明 f(n) = O((f(n))^2)。 （回想一下 Big-Oh 的定义，f(n) = O(g(n)) 当且仅当存在常量 c > 0, n0 使得 n >= n0, f(n) <= c * g(n)).

2)定理：如果f(n)和g(n)是从自然数到自然数的渐近正函数且f(n) = O(g(n))，则它 2^(f(n)) = O(2^(g(n)).

不一定为真

证明：证明是通过例子。可以证明 4n = O(2n)。 4n 和 2n 都是从自然数到自然数的渐近正函数。但是，也可以证明 2^(4n) = 16^n 不是 O(2^(2n)) = O(4^n).

3)定理：如果f(n)和g(n)是从自然数到自然数的渐近正函数且f(n) = O(g(n))，则它 g(n) = O(f(n)).

不一定为真

证明：证明是通过例子。可以证明 n = O(n^2)。 n 和 n^2 都是从自然数到自然数的渐近正函数。但是，也可以证明 n^2 不是 O(n).

Answer 2

1. f(n) = O((f(n))²)

默认情况下，任何函数本身都是大 O，即我们可以使用更大的常量 c_big 使得 f(n ) <= c_大.f(n).

因此，

• 如果 f(n) 小于或等于 c_big.f(n),
• 那么f(n)肯定会小于等于c_big.f(n).f(n),对于渐近正的f(n).

在数学上，f(n) = O(f(n).f(n)) = O(f(n)²) 为真。

---

2. f(n) = O(g(n)) implies 2^f(n) = O(2^g(n))

1. f(n) = O(g(n)) 意味着 f(n) <= g(n)
2. 另外，如果某个正数n小于m，那么2ⁿ 将小于 2^m
3. 利用上面的1.和2.，我们可以得出结论，如果f(n) = O(g(n))，那么2^f(n) = O( 2^g(n))

---

3. f(n) = O(g(n)) implies g(n) = O(f(n))

这个是错误的。

f(n) = O(g(n)) 意味着 g(n) = Ω(f(n))。

如果 f(n) = O(g(n))，则 f(n) 是 g(n) 的上界，这意味着 g(n) 是 f(n) 的下界，因此 g (n) = Ω(f(n)).