algorithm - 渐近符号性质证明？

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)。