是大欧米茄分配到加法？

Question

功能的大欧米总是等于所有子功能的大欧米？

例：

F(x) = a(x) + b(x) + c(x)...

big-omega(F(x) = big-omega(a(x)) + big-omega(b(x)) + big-omega(c(x))...

这总是真的吗？

对于像在数组中找到第i个最低值这样的事情是对的。

这是真的每个功能吗？

Answer 1

简短回答：是的，只要条款数量是固定的常数。如果术语的数量是可变的，它会变得有点棘手。

然而，对于一个有限数量而言的，它永远不会已经写出为后完成：

big-omega(a(x)) + big-omega(b(x)) + big-omega(c(x)) ... 

的原因是因为x变成任意大，术语的所有，但一会消失 - 要么因为具有相同的大欧米茄复杂性，要​​么被大欧米茄更大的复杂性所包容。

例子：

f(x) = x^3 + x^2 + x 
big-omega(f(x)) = big-omega(x^3 + x^2 + x) = big-omega(x^3) 

现在考虑：

f(x) = Summation(n = 1..x; n) 

在这里，我们知道，

Summation(n = 1..x; n) = x(x+1)/2 = x^2/2 + x/2 

所以， 大欧米茄（F扩展（X） ）=大-ω（x^2/2）+大-ω（x/2）=大-ω（x^2）

然而，使用原来的配方，可以考虑：

big-omega(Summation(n = 1..x; n)) != big-omega(1) + big-omega(2) + ... big-omega(n) 

应用大欧米茄在项之和是可变的，可能会导致混乱。