-4

関数は 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)   ?????
4

2 に答える 2

1

Ω(1)や Ω(x)と書くのは効率的ではないかもしれませんが 、それは正しいことです。Ω(x) は、漸近的にタイトな下限を定義します。したがって、漸近的に厳密ではない下限を定義するω表記を使用することをお勧めします。したがって、この特定の問題では、ω(x)またはω(1)は、Ω(x) または Ω(1) よりも実行時の複雑さをより適切に定義します。

于 2013-03-29T06:38:44.653 に答える
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。

于 2013-03-29T06:30:27.143 に答える