algorithm - 以下函数的渐近时间复杂度是多少？

Question

我在函数的渐近复杂度上遇到了这个问题：

3个函数的复杂度如下：

f(n) = O(n)

g(n) = 大欧米茄(n)

h(n) = θ(n)

那么结果函数[f(n).g(n)] + h(n)的渐近复杂度是多少

我可以通过初级命中和试验找出答案将是 Big-Omega(n)。例如，如果我说f(n) = n和g(n) = n和h(n) = n。所以我们可以说f(n) 是 O(n)并且g(n) 是 Big-Omega(n)并且h(n) 是 Theta(n)。现在f(n).g(n)是n ²，这将是Big-Omega(n) 但不是 O(n)。现在将其添加到 h(n) 是n ² +n。这也是Big-Omega(n) 但不是 Theta(n)。

但是我无法为此找到适当的逻辑或数学证明。有人可以帮我解决这个问题吗？

Answer 1

这是一个逻辑解释的尝试：

• f(n) = O(n)表示f的运行时间最多是线性的（可能是常数时间）。
• h(n) = Theta(n)表示h的运行时间是线性的。
• g(n) = Big-Omega(n)意味着它g的运行时间至少是线性的（可能是多项式，指数......我们不知道）。

现在让我们分析一下最好的情况：f(n)是常数时间，g(n)是线性的，h(n)是线性的。我们能对这个功能说些什么f(n)*g(n)+h(n)？它也是线性的。

对于最坏的情况，我们能说什么？什么g(n)都没有，因为我们对最坏情况下的行为一无所知。

所以我们可以得出结论，f(n)*g(n)+h(n) = Big-Omega(n)因为这个函数在最好的情况下是线性的。