algorithm - big-O での < または ≤ の使用

Question

O 記法の 2 つの異なる正式な定義を見てきました。

f(n) = O(g(n)) 定数 n ₀ , c がある場合、任意の n _{0 に対して}、f(n) < cg(n) となります

と

f(n) O(g(n)) 定数 n ₀ , c がある場合、任意の₀の場合、f(n) ≤ cg(n) となります

違いは、f(n) が厳密に cg(n) よりも小さいか、cg(n) 以下であるかです。

これらの定義は同じですか? もしそうなら、どうやってそれを証明するのですか？

Answer 1

手始めに、あなたがそれを持っているなら

f(n) < cg(n) 任意の n ≥ n ₀

それからそれはまた事実です

_{任意の n ≥ n 0}に対して f(n) ≤ cg(n) 。

同様に、

_{任意の n ≥ n 0}に対して f(n) ≤ cg(n)

g(n) ≥ 1 と仮定すると、任意の n ≥ n ₀について、

f(n) ≤ cg(n) ≥ cg(n) + 1 ≤ cg(n) + g(n) = (c + 1)g(n)

したがって、新しい定数 c' = c + 1 を使用すると、次のようになります。

f(n) < c' g(n) for any n ≥ n ₀

お役に立てれば！