首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如果f(n)是Θ(h(n))且g(n) = O(h(n)),则f(n) + g(n)是Θ(h(n))。对或错

对。

根据大O符号的定义,如果f(n)是Θ(h(n)),则存在正常数c1和c2,以及某个正整数n0,使得对于所有n≥n0,有c1h(n)≤f(n)≤c2h(n)。

同样地,如果g(n) = O(h(n)),则存在正常数c3和某个正整数n1,使得对于所有n≥n1,有g(n)≤c3*h(n)。

现在考虑f(n) + g(n),对于所有n≥max(n0, n1),有: f(n) + g(n) ≤ c2h(n) + c3h(n) = (c2 + c3)*h(n)

另一方面,对于所有n≥max(n0, n1),有: f(n) + g(n) ≥ c1h(n) + 0 = c1h(n)

因此,f(n) + g(n)是Θ(h(n))。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

领券