Является ли Big-Omega дистрибутивным для добавления?

Question

Является ли большая омега функции всегда равной большой омеге всех подфункций?

Ex:

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)) ... 

Причина в том, что при х становится сколь угодно большим, все, кроме одного из слагаемых исчезнет - либо из-за того, что они имеют одинаковую сложность с большой омегой, либо из-за более крупных крупных омега-сложностей.

Пример:

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 

Так, большой омега (ф (х)) = большая-омега (x^2/2) + большая-омега (x/2) = большая-омега (x^2)

Однако, используя оригинальную формулу, рассмотрим:

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

Применение большого омега над суммой слагаемых, переменной может привести к путанице.