big-o - O(n^2) が Θ(n^2) と同じなのはなぜですか?

Question

今日、私たちの教授は、O(n^2) は Θ(n^2) と同じだと言いました。

私はその説明を理解できず、インターネット上で何かを見つけることができませんでした. 誰か説明してくれませんか？

どうもありがとうございました。

Answer 1

それは真実ではない。たとえば、n = O(n ² ) (c = 1、n ₀ = 0 を選択) ですが、Θ(n ² ) ではありません (lim _n→∞ n / n ² = 0 のため)。あなたがインストラクターの言葉を聞き間違えたか、彼らが言い間違えたか、または一般化されていないことが真実である特定の文脈について話しているのではないかと思います。

お役に立てれば！

Answer 2

それは同じではありません。O は上限、Ω は下限、Θ は上限と下限の両方です。

例として、関数 f(n) = n は O(n^2) ですが、 n^2 の倍数で下から f を制限できないため、Θ(n^2) ではありません。

Answer 3

Big O は上限のみを示します。Θ も下限を示します。このSO Questionは役立つはずです。教授が逆のことを言うなら、あなたの教授は正しいでしょう。参照された質問で述べたように：

Θ(f(n)) も O(f(n)) ですが、その逆ではありません。