クラスでbig-oの学習を始めたばかりです。すべての x>k |f(x)|<=c|g(x)|. 署名するために <= を含める必要があるかどうか、または < 記号を入れるだけで十分かどうかという質問がありました。
例: f(x)=17x+11 とすると、これが O(x^2) であることを証明します。次に、c=28 で x>k=1 とすると、17x+11<=28x^2 となります。x は常に 1 より大きいことがわかっているので、これは 28x^2 が常に 17x+11 より大きいことを意味します。では、本当に等号 (<=) を含める必要があるのでしょうか、それとも (<) だけでよいのでしょうか。
前もって感謝します。
から| f ( x )| ≤ c | g ( x )| 実数値のcについては、次のようになります。f ( x )| < ( c + e ) | g ( x )| すべてのe > 0 に対して。
このことから、| を満たすようなc' = ( c + e )が存在することがわかります。f ( x )| < c' | g ( x )| であるため、≤ の代わりに < を使用できます。
より実際的には、証明できれば | f ( x )| < c | g ( x )| の場合、≤ の部分は自明です。
<=記号を含める必要があるかどうか、または<記号を付けるだけで十分かどうか。
あなたがここで尋ねている2つのわずかに異なることがあります、私は思います：
あなたがすべてのためにとそのようなことを示すことができるなら、自明にあなたはすべてのためにcとそのようなことも示しました。したがって、表示するだけで十分ですが、次のようになります。kx > k |f(x)| <= c|g(x)|ckx > k |f(x)| < c|g(x)|<
あなたが述べたように、言うことができるための実際の要件は、すべてのためにとそのようなものf(x) = O(g(x))を見つけることです。私たちができる最善のことは、すべての人にとってaとそのようなものを見つけることである場合、私たちはあなたの条件を満たしていませんが、示すのに十分なことをしました。したがって、表示する必要はありませんckx > k |f(x)| <= c|g(x)|ckx > k |f(x)| = c|g(x)|<f(x) = O(g(x))<
x < y を示した場合は、x <= y も示しています。だから違いはありません。