如何评估以下涉及渐近符号的表达式？

Question

如果

f(n)=ϴ(n),g(n)=ϴ(n)

和

h(n)=Ω(n)

那怎么评价f(n)g(n)+h(n)？

我接近f(n)g(n)=ϴ(n^2)，现在会是Ω(n)+ϴ(n^2)。根据我的说法，这个表达式的下界应该是 Ω(n)，上限应该是 O(n^2)，但是这个表达式的最紧界应该是什么？

Answer 1

对于某些常量 k1, k2, l1, l2 and m > 0，我们有：

f(n) is ϴ(n)

    => k1*n < f(n) < k2*n, for n sufficiently large

g(n) is ϴ(n)

    => l1*n < g(n) < g2*n, for n sufficiently large

h(n) is Ω(n)

    => m*n < h(n), for n sufficiently large

然后，f(n)*h(n):

for f(n) * h(n): 

    k1*l1*n^2 < f(n)*g(n) < k2*l2*n^2, for n sufficiently large

所以我们可以只写 p(n) = f(n)*g(n) 并使用常量 c1=k1*l1 和 c2=k2*l2，我们有：

p(n) (= f(n)*g(n)) is in ϴ(n^2), since

    c1*n^2 < p(n) < c2*n^2

那么，最后，p(n) + h(n)有什么复杂性呢？我们有：

c1*n^2 + m*n < p(n) + h(n), for n sufficiently large

由于我们从未获得 h(n) 的上限，因此我们无法真正说明 p(n) + h(n) 的上限。这是势在必行的：h(n) in Ω(n) 只是说 h(n) 至少和 n 一样快（线性）渐近增长，但我们不知道这是否是一个严格的下限。对于指数时间函数来说，这可能是一个非常草率的下界。

接下来，我们只能说下界的事情：

p(n) + h(n) = f(n)*g(n) + h(n) is in Ω(n^2)

即，f(n)*g(n) + h(n) 至少随着 n^2 渐近增长（即，在 Ω(n^2) 中）。

关于您的方法的注释：您是正确的（如上所示）f(n)g(n) is in ϴ(n^2)，但请注意，这意味着 f(n)g(n) + h(n) 的严格下限永远不会小于 k*n^2：即 f(n)g(n) + h(n) in Ω(n^2) 是给定的，并且比您建议的下限更好（更严格）； Ω(n)。回想一下，增长最快的项支配渐近行为。

作为参考，请参见示例

https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation

如何评估以下涉及渐近符号的表达式？

How to evaluate below expression involving asymptotic notations?

algorithm

asymptotic-complexity