我正在研究 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)
的值到底得出了什么结论?
最佳答案
证明 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))
的定义在问题陈述中给出。
希望这对您有所帮助。
关于algorithm - 渐近增长 : Understanding the specific proof of f(n) + little o(f(n)) = theta (f(n))?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52276455/