Big-Omega는 추가로 배포됩니까?

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) 

, 우리가 알 수 있도록 큰 오메가 (F

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

의 확장 (X)) = 큰 오메가 (x^2/2) + 큰 오메가 (x/2) = 큰 오메가 (x^2)

그러나, 원래의 공식을 사용하여, 고려 :

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

을 혼란으로 이어질 수있는 변수가 용어의 합 이상 큰 오메가 적용.