2

我试图证明如果 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))

4

2 回答 2

1

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

证明:因为 f(n) 是从自然数到自然数的渐近正函数,所以保证对于所有自然数 n 大于或等于某个自然数 n0,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 都是从 naturals 到 naturals 的渐近正函数。但是,也可以证明 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)。

于 2017-12-05T21:25:43.147 回答
1
  1. f(n) = O((f(n)) 2 )

默认情况下,任何函数本身都是大 O,即我们可以使用更大的常数c big使得 f(n) <= c big .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 ) 为真。


  1. f(n) = O(g(n)) 意味着 2 f(n) = O(2 g(n) )
  1. f(n) = O(g(n)) 意味着 f(n) <= g(n)
  2. 此外,如果某个正数n小于m,则 2 n将小于 2 m
  3. 使用上面的 1. 和 2.,我们可以得出结论,如果 f(n) = O(g(n)),则 2 f(n) = O(2 g(n) )

  1. f(n) = O(g(n)) 意味着 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))。

于 2017-12-05T21:58:37.413 回答