如何展示big-theta的传递性？

Question

如果我有函数f(x)，g(x)和h(x)，使得f(x)是Θ( g(x) )，g(X)是Θ(h(x))。我如何证明f(x)是Θ(h(x))。我可以通过证明f(x)是h(x)的大O和大ω来解决这个问题吗？如果是这样的话，我该怎么做呢？

Answer 1

我可以通过证明f(x)既是h(x)的大o又是h(X)的大ω来解决这个问题吗？

？

是的，你可以这样做。

，如果是这样的话，我该怎么做呢？

一种方法是使用Big O和Big Omega的定义。

证明大O(大Omega类似)：

根据definition of big Theta，f(n) = Θ(g(n)) iff f(n) = O(g(n)) 和 f(n) = Ω(g(n))。

由于f(n) = O(g(n))，那么根据大O的定义，存在c_0 > 0和N_0 > 0，使得对于每个n > N_0，

(1) f(n) <= c_0 * g(n)

类似地，由于g(n) = O(h(n))，那么根据大O的定义，存在c_1 > 0和N_1 > 0，使得对于每个n > N_1，

(2) g(n) <= c_1 * h(n)

如果我们定义N_2 = max{N_0, N_1}和c_2 = c_0 * c_1，那么对于我们得到的每个n > N_2：

f(n) <= c_0 * g(n) <= c_0 * c_1 * h(n) = c_2 * h(n)

第一个不等式成立，因为n > N_0 (从n > N_2开始)和我们可以使用(1)。自n > N_1以来，第二个不等式成立，我们可以使用(2)。

因此，根据定义f(n) = O(h(n))。

在我们展示了f(n) = Ω(h(n))之后，我们可以根据大θ的定义得出f(n) = Θ(h(x))的结论。