ビッグオメガは追加に配布されていますか？

Question

関数のbig-omegaは、すべてのsub-functionのbig-omegaと常に等しいですか？

例：

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

短い答え：はい、用語の数は固定定数です。しかし、用語の数が可変であれば、少し難解になります。

として書き出された後しかし、用語の有限数のために、それは完全ではありません：xは任意の大きさになると、用語のうちの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) 

は、私たちが知っているので、 ビッグオメガ（F

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

の拡張（X） ）= big-omega（x^2/2）+ big-omega（x/2）= big-omega（x^2）

しかし、元の式を使用して、検討してください。

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

を混乱につながる可能変数である項の和の上にビッグオメガ適用します。