algorithm - 函数 f(x) = x^2+x+1 的下界？

Question

函数是 f(x) = x^2+x+1

   **Upper Bound**
 when x>0,
              x^2 >= x^2    
  similarly,  x >= x^2   
   and,    
              1 >= x^2

    therefore,  f(x)=x^2+x+1  >= x^2+x^2+x^2   (all sufficient large value of x)
                              >= 3x^2     , where c=3 

                           f(x)= O(x^2)

  **Lower Bound**

        f(x)=x^2+x+1 >= x^2
                  f(x) = Ω(x^2)

> 但是我们可以把它的下限写成 Ω(x) 和 Ω(1) 因为

              f(x)=x^2+x+1  >= x    (all sufficient large value of x)
                      f(x)  = Ω(x)  ??

和

             f(x)=x^2+x+1 >= 1   (all sufficient large value of x)
                      f(x)  = Ω(1)   ?????

Answer 1

是的，我们绝对可以把它写成 w(n) 甚至 w(1)。然而，这根本没有意义，因为我们正在寻找最高的 Ω。（Ω 将用小欧米茄而不是这个大欧米茄来表示c . g(n) < f(n)。如果我们使用 Ω，那意味着c . g(n) <= f(n)）。

c . g(n) < f(n)意味着：不存在c将 g(n) 扩大为 的常数g(n) = f(n) for all n >= 0。

Answer 2

好吧，写Ω(1)或 Ω(x)可能效率不高 ，即使它是正确的。Ω(x) 定义了一个渐近紧密的下界。所以最好使用定义渐近不紧下界的ω符号。因此，在这个特定问题中，ω(x)或ω(1)比 Ω(x) 或 Ω(1) 更好地定义了运行时间复杂度。