是大歐米茄分配到加法？

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) 

應用大歐米茄在項之和是可變的，可能會導致混亂。