式の両辺で漸近表記

Question

f(n)=theta(g(n))またはf(n)=BighOh(g(n))の意味は分かっていますが、theta(f(n)) = theta(g(n))のようなものがあると混乱します。すなわち、漸近表記が両側にある場合には、誰でもこの意味は何を説明できますか？

このような問題を解決するとき、私は、これを得た：3アルゴリズムは

X : is polynomial 
Y : is exponential 
Z : is double exponential 

ある答えで4 opitionsあります

a) theta(X) = theta(Y) 
b) theta(X) = theta(Z) 
c) theta(Y) = theta(Z) 
d) BigOh(Z) = X 

が正しい答えはオプションC. できることです誰でも説明してください

Answer 1

C = θ(D)、簡単な言葉で言えば、2タイトな境界があると言うと、Aとこれらの間にCを挟むようにしてもよい。つまり、A <= C <= Bです。

AおよびBは、Dに依存します。つまり、A = aDとB = bDここで、aとbは定数です。一般theta(P) = theta(Q)に

P (aP and bP)とQ (aQ and bQ)

• によって指定された境界が等しい即ち、aP = aQ及びbP = bQ、または別の すなわち、aP<=aQ<=bQ<=bP又はaQ<=aP<=bP<=bQ内部に収容における境界の

• 一つであることを意味します。ここ

  Y = exponential = 1.5^x 
  Z = double exponential = 1.5^1.5^x 
  

、指数関数（1.5^x）上の境界が二重指数関数（1.5^1.5^x）の境界を含むことができることgraphから見ることができます。従ってθ(Y) = θ(Z)。事実、指数関数の境界は二重指数関数の境界として使用できます。