方程兩側的漸近表示法

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和B這樣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 
  

在這裏，它可以從所述graph可以看出，在指數函數（1.5^x）的範圍可含有雙重指數（1.5^1.5^x）的邊界。因此θ(Y) = θ(Z)。事實上，指數函數的界限可以用作雙指數函數的界限。