algorithm - 小さな o(g(n)) は、Theta(g(n)) と O(g(n)) の設定差ですか?

Question

直感的にはイエスのようです。だれか真剣な証明をしてくれませんか?

Answer 1

答えはノーだ。これを確認するには、各漸近限界の正式な定義に戻る必要があります。

Big O(g(n)) = { f(n): すべての n ≥ n0 に対して 0 ≤ f(n) ≤ cg(n) となるような正の定数 c および n0 が存在する}。//これは漸近的な上限です。47 ページ (以下の引用を参照)。

Theta(g(n)) = { f(n) : すべての n ≥ n0 に対して 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) となる正の定数 c1、c2、および n0 が存在する}。44 ページ。// これは漸近的にタイトな境界です。

小さな o(g(n)) = { f(n) : 任意の正の定数 c > 0 に対して、すべての n ≥ n0 に対して 0 ≤ f(n) < cg(n) } となる定数 n0 > 0 が存在します。Pg 50. これは、タイトではない漸近的な上限を示します。

Big Omega(g(n)) = { f(n): すべての n ≥ n0 に対して 0 ≤ cg(n) ≤ f(n) となる正の定数 c および n0 が存在する}. 48 ページ。これは漸近的な下限です。

Theta は漸近的にタイトな上限です。つまり、Big O と Big Omega は、Theta を保持するために保持する必要があります。それぞれの定義は実際にはセットであるため、シータはセット Big O と Big Omega の和集合として理解できます。したがって、セットの違いは、シータ - ビッグ O = ビッグ オメガです。少しではありません。

定数がすべてのセットで同じに保持されていない場合、答えは少しどろどろになることに注意してください。

引用：スタイン、クリフォード。「第3章 機能の成長」アルゴリズムの紹介。トーマス・H・コーメン、チャールズ・エリック著。Leiserson、およびRonald L. Rivest。第3版。マサチューセッツ州ケンブリッジ: MIT、2009 年。N. ページ。印刷します。

Answer 2

それは真実ではない。取った：

f(n) = (floor(n/2))!
g(n) = (ceil(n/2))!

次に、次のようになります。

f  = O(g)      since f(n) <= g(n)
f != o(g)      since f(n) = g(n) for unbounded n (even)
f != Theta(g)  since f(n) * ceil(n/2) <= g(n) for unbounded n (odd)

したがって、 f は にありますO(g)\Theta(g)が、 にはありませんo(g)。