我正在研究f(n) + o(f(n)) = theta (f(n))的证明，我在证明中遇到了一部分，表明我难以理解。
我们让f(n)和g(n)成为渐近正函数并假设g(n) = O(f(n))。 在证明中，它指出，既然我们知道f(n) + g(n) ≥ f(n)适用于所有n，我们可以得出结论，f(n) + g(n) = Omega((f(n))。 我们也可以得出类似的结论，f(n) + g(n) ≤ 2 f(n).因此f(n) + g(n) = O(f(n)). 我很难理解为什么f(n) + g(n) = Omega((f(n))和f(n) + g(n) = O(f(n))都是真的。我们如何证明紧下限是当我们向f(n)加g(n)时？我们从g(n)的价值中得出的确切结论是什么？
证明f(n)是theta(g(n))的一种方法是证明两个独立的陈述：f(n)是omega(g(n))，f(n)是O(g(n))。很明显，从这些符号的定义来看，这种证明方式是正确的。
在这个确切的问题中，如果我们选择某个常数c等于1，对于每个n，我们将有该f(n) + g(n) >= c * f(n)，因此，根据定义，表明f(n) + g(n)是Omega(f(n))。此外，对于O(f(n))部分，如果我们选择在这种情况下要2的常数c，我们需要证明存在一些n0，使得每个n > n0f(n) + g(n) <= c * f(n)，这相当于每个n > n0的g(n) <= f(n)，这等价于问题陈述中给出的g(n) = O(f(n))定义。
希望这有帮助。