[解決済み] ビッグ・オー vs ビッグ・シータ【重複あり

質問

重複の可能性があります。
Θ(n)とO(n)の違いは何ですか？

アルゴリズムの複雑さについて非公式に話すときは、ビッグ・オーについて話すような気がします。しかし、正式な場では、私はしばしばbig-θを目にし、時折big-ohも混じります。 この2つの違いは数学的には分かっているのですが、英語では、big-thetaを意味するときにbig-ohを使うのはどんな状況で間違っているのでしょうか（アルゴリズムの例があればありがたいです）。

おまけ：なぜ人々は非公式に話すとき、いつもbig-ohを使うように見えるのでしょうか？

どのように解決するのか？

Big-Oは上界です。

Big-Thetaはタイトバウンド、つまり上限です。 と 下限値

つまり、「これより悪くなることはない」ということです。もちろん、境界は厳密であればあるほどよいのですが、厳密な境界を計算するのは必ずしも容易ではありません。

こちらもご覧ください

• ウィキペディア/ビッグ・オー記法

関連する質問

• Θ(n)とO(n)の違いは何ですか？

Wikipediaの次の引用文も光明を与えています。

非公式に、特にコンピュータサイエンスでは、しばしばビッグ・オー表記が使われます。 漸近的な厳しさを表現するために、多少乱用することが許されています。 ビッグシータ表記の方が事実上適切な場合があります。 あるコンテキストで

例えば、ある関数を考えるとき T(n) = 73n ³ + 22n ² + 58 は、一般にすべて許容されるが、通常、境界の緩さ（すなわち、以下の箇条書き2および3）よりも境界の厳しさ（すなわち、箇条書き1）が強く好まれる。 を使用する。）

1. T(n) = O(n ¹⁰⁰ ) と同じである。 T(n) ∈ O(n ¹⁰⁰ )
2. T(n) = O(n ³ ) と同じである。 T(n) ∈ O(n ³ )
3. T(n) = Θ(n ³ ) と同じである。 T(n) ∈ Θ(n ³ )

それぞれ相当する英文は以下の通りです。

1. T(n) よりも漸近的に速く成長することはありません。 n ¹⁰⁰
2. T(n) よりも漸近的に速く成長することはありません。 n ³
3. T(n) と同じ漸近的な速さで成長する。 n ³ .

つまり、3つのステートメントはすべて真実であるが、徐々に多くの情報が含まれているのである。 があります。しかし、分野によっては、ビッグ・オー表記（上のリストの2番目の箇条書き）、つまり ビッグシータ表記（箇条書きで3番）よりも、より一般的に使用されるでしょう。 のように、ゆっくり成長する関数の方が望ましいからである。