notation - ビッグシータ表記法を解く

Question

大きなシータ表記の解決に問題があります。大きな O 表記は最悪のケースと上限を表し、オメガ表記は最良のケースと下限を表すことを理解しています。

O(nlogn) 時間と Omega(n) で実行されるアルゴリズムが与えられた場合、どのように Theta が等しいかを推測できますか? O と Omega が等しい場合にのみ、シータ表記が存在すると仮定し始めていますが、これは本当ですか?

Answer 1

アルゴリズムがで実行されると仮定しますf(x)。

f(x) = O(n*log(n))つまり、x十分に高い場合は定数が存在するc1 > 0ため、f(x)常に。よりも小さくなりc1*n*log(n)ます。

f(x) = Omega(n)x十分に高い場合、定数が存在するc2 > 0ためf(x)、c2*n

したがって、今知っているのは、特定の時点以降（x十分に大きい）、アルゴリズムがより速く、c2*nより遅く実行されるということだけc1*n*log(n)です。

f(x) = Theta(g(x))x十分な大きさの場合、いくつかあることc3 > 0を意味します。c4 > 0したがってc3*g(x) <= f(x) <= c4*g(x)、これはf(x)、一定の係数をより速くまたは遅く実行することを意味しg(x)ます。だから確かに、f(x) = O(g(x))そしてf(x) = Omega(g(x))。

結論： Oとオメガだけが与えられているので、それらが同じでなければ、シータが何であるかを結論付けることはできません。アルゴリズムがあれば、Oが高すぎるか、Omegaが低すぎるかを試してみることができます。