big-o - O(1) と Θ(1) の違いは何ですか?

Question

私は両方の定義を知っていますが、教科書に O(1) と Θ(1) が書かれていることがあるのはなぜですか?

ありがとう。

Answer 1

O(1) と Θ(1) は、実数上の関数について話している場合、必ずしも同じではありません。たとえば、関数 f(n) = 1/n を考えてみましょう。この関数は O(1) です。これは、n ≥ 1 の場合、f(n) ≤ 1 であるためです。しかし、次の理由により、これは Θ(1)ではありません: f(n) = Θ(g(n)) の 1 つの定義それが |f(n) / g(n)| の限界です。n が無限大になると、0 < L を満たす有限値 L になります。f(n) = 1/n および g(n) = 1 を代入すると、|1/n| の極限が得られます。n は無限大になり、0 になるため、f(n) ≠ Θ(1) です。

お役に立てれば！

Answer 2

Big-O 表記は漸近的な上限を表し、Big-Theta 表記はさらに漸近的な下限を表します。多くの場合、上限は人々が関心を持っているものであるため、Theta(何か) も真である場合でも、O(何か) と書きます。たとえば、並べ替えられていないリストで x に等しいものの数を数えたい場合、線形時間で実行でき、O(n) であると言うかもしれません。それ以上かかることはありません。ただし、リスト内のすべての要素を調べる必要があるため、Omega(n)、したがって Theta(n) であることも事実です。サブリニア時間では実行できません。

アップデート：

正式には：

• O(g) の f は、すべての n > n0 に対して f(n) <= c * g(n) となる ac と n0 が存在する場合に限ります。

• すべての n > n0 に対して f(n) >= c * g(n) となる ac と n0 が存在する場合、Omega(g) の f。

• f in Theta(g) if f in O(g) and f in Omega(g), すなわち、すべての n > n0 に対して c1 * g(n) <= f となるような c1、a c2、および n0 が存在する場合(n) <= c2 * g(n)。