我理解大哦和theta。问题如下，证明或反证： f(n) = theta(g(n) => h(f(n)) = O(h(g(n))) 如果 h(n) 是一个递增函数. h(n1) > h(n2) 当 n1 > n2
所以，在上面的问题中，我停留在理解递增函数的点上。如果我试图找到一些函数来反驳它，例如，n 和 2n 这可以接受吗？becos big-oh 代表快速增长，而不仅仅是一个常数因子，但没有定义 h(n) 函数的这种条件（我的意思是，我认为 > 字面上比这里大，这是错误的吗？）
另外，即使我发现像 h(f(n)) 这样的东西以与 h(g(n)) 相同的速度增长，这意味着它们本质上是 theta，它们仍然很大吗？因为 theta 的松散界限很大，在这种情况下，我永远无法反驳上述说法。
如果我的理解在通过序列时的某个时刻出现偏差，请纠正我。谢谢！
我找到了一个矛盾的例子来解决这个问题，通过采用f(n) = 2n并且g(n) = n满足给定的f(n) = theta(g(n)).
现在，让h(x) = 2^x，这意味着h(f(n)) = 2^2n = 4^n和h(g(n)) = 2^n。
根据定义，这意味着h(g(n)) = O(h(f(n))). 因此被反驳。
我从来不知道矛盾的例子足以反驳。我正在尝试一种更正式的方式来证明这一点，但我却搞砸了细节。
谢谢。
我总是通过重新阅读然后写下 Theta(f) 和 O(f) 的定义来开始这样的问题。如果你能找到一个反驳这个断言的简单例子，你就不需要证明任何东西。我喜欢快速增长的 h(x) 的想法，例如 h(x) = 2^x。那么如果你有例如 f(x) = 2x, g(x) = x, h(f(x)) = 2^(2x), h(g(x)) = 2^x 和 h(f(x )) / h(g(x)) = 2^x - 尝试将这些插入到您的定义中，看看会发生什么。请注意，由于 f(x) = 2g(x)，至少根据我的定义，你有 f(x) = Theta(g(x)) 和 g(x) = Theta(f(x))