algorithm - 渐近增长 : Understanding the specific proof of f(n) + little o(f(n)) = theta (f(n))?

Question

我正在研究 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)) 为真。当我们将 g(n) 添加到 f( n)？我们从g(n)的值到底得出了什么结论？

Answer 1

证明 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))部分，如果我们选择常量 c成为2在这种情况下，我们需要证明存在一些 n0这样 f(n) + g(n) <= c * f(n)对于每个 n > n0 ，相当于 g(n) <= f(n)对于每个 n > n0 ，相当于 g(n) = O(f(n)) 的定义在问题陈述中给出。

希望这对您有所帮助。