時々、Θ(n) の真ん中に何かがある奇妙な Θ 記号が表示され、また O(n) だけが表示されることがあります。誰もこの記号の入力方法を知らないため、単に入力が面倒なのでしょうか、それとも別の意味があるのでしょうか。
ベストアンサー1
簡単な説明:
アルゴリズムがΘ(g(n))である場合、n(入力サイズ)が大きくなるにつれてアルゴリズムの実行時間がg(n)に比例することを意味します。
アルゴリズムが O(g(n)) の場合、n が大きくなるにつれてアルゴリズムの実行時間は最大でg(n) に比例することを意味します。
通常、O(g(n)) について話すときも、実際には Θ(g(n)) を意味しますが、技術的には違いがあります。
より技術的に言えば：
O(n) は上限を表します。Θ(n) は厳密な境界を意味します。Ω(n) は下限を表します。
f(x) = Θ(g(x)) かつ f(x) = O(g(x)) かつ f(x) = Ω(g(x)) の場合に限る
基本的に、アルゴリズムが O(n) であると言う場合、それは O(n 2 )、O(n 1000000 )、O(2 n )、... でもありますが、Θ(n) アルゴリズムはΘ(n 2 ) ではありません。
実際、f(n) = Θ(g(n)) は n が十分に大きい場合を意味するため、c 1と c 2のある値に対して f(n) は c 1 g(n) と c 2 g(n) の範囲内で制限される可能性があります。つまり、f の成長率は漸近的に g に等しくなります。g は f の下限値と上限値になることができます。これは、f が g の下限値と上限値にもなり得ることを直接的に意味します。したがって、
f(x) = Θ(g(x)) かつ g(x) = Θ(f(x)) である
同様に、f(n) = Θ(g(n)) を示すには、g が f の上限 (つまり f(n) = O(g(n))) であり、f が g の下限 (つまり f(n) = Ω(g(n))) であることを示すだけで十分です。これは g(n) = O(f(n))) とまったく同じです。簡潔に言うと、
f(x) = Θ(g(x)) かつ f(x) = O(g(x)) かつ g(x) = O(f(x)) の場合に限る
ω関数の緩い上限と緩い下限を表す、小文字のオーと小文字のオメガ ( ) 表記もあります。
要約する：
f(x) = O(g(x))(big-oh) は、 の成長率がの成長率に対してf(x)漸近的に小さいか等しいg(x)ことを意味します。
f(x) = Ω(g(x))（大オメガ）は、の成長率f(x)が漸近的に成長率以上であることを意味する。g(x)
f(x) = o(g(x))(小文字のオー) は、 の成長率がの成長率よりもf(x)漸近的に小さいg(x)ことを意味します。
f(x) = ω(g(x))（小オメガ）は、の成長率がf(x)漸近的に成長率よりも大きいことを意味します。g(x)
f(x) = Θ(g(x))(theta)は、の成長率がf(x)漸近的に成長率に等しいことを意味する。g(x)
さらに詳しい議論については、Wikipediaの定義を読むまたは、Cormen らによる「Introduction to Algorithms」などの古典的な教科書を参照してください。