如何证明big-theta（大Θ）渐近符号的传递性？

首先可以明确：你提到的「先分别证明f(x)是h(x)的大O和大Ω」是完全正确的思路，这是由大Θ的定义直接决定的——大Θ的本质就是对函数上下界的同时约束，只有同时满足大O（上界）和大Ω（下界）的要求，才能判定Θ关系成立。

我们先明确大Θ的标准定义：对于两个非负函数a(x)和b(x)，a(x) = Θ(b(x))当且仅当存在正的常数c₁、c₂和足够大的阈值x₀，使得对所有x ≥ x₀，都有 c₁·b(x) ≤ a(x) ≤ c₂·b(x)。

第一步：列出已知条件的约束 #

根据题设给出的两个Θ关系，我们可以直接得到两组约束：

• 由f(x) = Θ(g(x))：存在正常数c_f1、c_f2和阈值x_f，对所有x ≥ x_f，满足：

  c_f1 · g(x) ≤ f(x) ≤ c_f2 · g(x)

• 由g(x) = Θ(h(x))：存在正常数c_g1、c_g2和阈值x_g，对所有x ≥ x_g，满足：

  c_g1 · h(x) ≤ g(x) ≤ c_g2 · h(x)

第二步：证明f(x)是h(x)的大O（上界约束） #

取阈值x₁ = max(x_f, x_g)，对所有x ≥ x₁，两组约束同时成立：
将g(x)的上界代入f(x)的上界不等式，可得：
f(x) ≤ c_f2 · g(x) ≤ c_f2 · c_g2 · h(x)
其中c_f2·c_g2是正的常数，阈值x₁满足大O的定义要求，因此f(x) = O(h(x))得证。

第三步：证明f(x)是h(x)的大Ω（下界约束） #

同样取阈值x₁ = max(x_f, x_g)，将g(x)的下界代入f(x)的下界不等式，可得：
f(x) ≥ c_f1 · g(x) ≥ c_f1 · c_g1 · h(x)
其中c_f1·c_g1是正的常数，阈值x₁满足大Ω的定义要求，因此f(x) = Ω(h(x))得证。

第四步：合并得到Θ结论 #

因为f(x)同时满足f(x) = O(h(x))和f(x) = Ω(h(x))，根据大Θ的定义，可直接得出f(x) = Θ(h(x))，这也验证了大Θ关系具有传递性。

内容的提问来源于stack exchange，提问作者Smiley2002