algorithm - 等式两边的渐近符号

Question

我知道 f(n)=theta(g(n)) 或 f(n)=BigOh(g(n)) 是什么意思，但我很困惑当有类似 theta(f(n)) = theta(g(n)) 的时候。即当渐近符号在两侧时。谁能解释一下这是什么意思？

我明白了，在解决这样的问题时:有 3 种算法

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

答案有4个选项:

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) .实际上指数函数的界可以作为双指数函数的界。