gpt4 book ai didi

algorithm - 如果 f(n) = o(g(n)),g(n) + f(n)=Θ(g(n)) 吗?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:17:37 29 4
gpt4 key购买 nike

如果我设法证明 f(n) = o(g(n))(小 o),那么这两个函数的总和 f( n) + g(n) 应该被“更大”的函数 g(n) 紧紧束缚。

然而,我在证明这一点时遇到了一些麻烦。

最佳答案

以下推理显示了渐近恒等式 (Theta) 意义上的“紧界”:

    f = o(g)
<=> lim_n->oo ( f(n)/g(n) ) = 0
=> lim_n->oo ( (f(n)+g(n))/g(n) )
= lim_n->oo ( f(n)/g(n) ) + lim_n->oo ( g(n)/g(n) )
= 0 + 1

关于algorithm - 如果 f(n) = o(g(n)),g(n) + f(n)=Θ(g(n)) 吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29139448/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com