algorithm - 異なる漸近記法の乗算と加算

Question

誰かがそのような計算を実行する方法を知っていますか例:

O(n^2) + THETA(n) + OMEGA(n^3) = ?

また

O(n^2) * THETA(n) * OMEGA(n^3) = ?

一般に、さまざまな漸近記法を加算および乗算する方法は?

Answer 1

O上限を与える;

Ω下限を与える;

Θ漸近限界を与える;

ウィキペディアには、これらを説明する優れたチャートがあります。

したがって、これらは一般的に比較することはできません。

最初のケースでは、

O(n^2) + Θ(n) + Ω(n^3)

まずは取り組みましょうO。第 1 項は私たちに教えてくれO(n^2)、第 2 項は私たちに教えてくれO(n)ます。これら 2 つだけに基づいて、これまでのところO(n^2)上限があることがわかります。しかし、第 3 項は上限について何も教えてくれません! したがって、については何も結論付けることはできませんO。

ここでのポイントは、Oおよびのみに関する情報を提供し、 および のみに関するΘ情報を提供することです。これは、と の両方を意味するため、与えられた分析に適したとのいずれかに変更できるためです。OΩΘΩΘ(g(n))O(g(n))Ω(g(n))ΘOΩ

ただし、これら 3 つを一緒に使用したり、 と だけOを使用したりすると、 も も他のものについて何も意味しΩないため、わかりません。OΩ

Answer 2

できません。と を知っているa > 0としb < 10ます。についての情報はありませんa+b。それは何でもかまいません。

Big-O と Big-Omega は、関数に対して同様に機能します。

Answer 3

私の上記の答えは一般的な関数と境界に対して正しいですが、コンピューター サイエンスでは通常、正の関数のみを考慮します。したがって、最初の例では、次のようになります。

O(n^2) + Theta(n) + Omega(n^3) = Omega(1)+Theta(n)+Omega(n^3) = Omega(n^3)

これは、関数がすべて正であるという仮定に由来します。つまり、すべての関数はOmega(1).