big-theta - ビッグシータ問題

Question

私には2つの機能があります：

• f（n）= 2;
• g（n）= 10 ^ 100;

f（n）= BigTheta（g（n））かどうかを正当化する必要があります。

私の推測では、両方の関数が定数であるため（関数が比例していることを意味します）、f（n）はBigTheta（g（n））ですが、私の先生は私が間違っていると主張しています。

私は正しいですか？ケースを休める方法はありますか？これが初心者の質問のように聞こえたらごめんなさい！ありがとう。

Answer 1

あなたは正しいです。あなたが問題を正しく引用し、誤解がないと仮定すると、彼らがお互いのシータではないと言った場合、あなたの先生は間違っています。

定義は次のとおりです。

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

明らか|100^10|*k1 <= |2| <= |100^2|*k2に定数k1=1/100^10およびk2=1（すべてのxが適切なカットオフ値よりも大きい場合x_cutoff）

ただし、試験問題の実際のテキストと、あなたが書いた（または丸で囲んだ）正確なテキストを知らなければ、インターネット上で問題のある種の誤読がないことを知る方法はありません。また、あなたの答えが正しいとしても、あなたはあなたの正当化においてまだ間違っている可能性があることに注意する必要があります。

レコードの場合、セットに含まれているだけでなくf(x)、セットBigTheta(g(x))にも含まg(x)れていますBigTheta(f(x))。同等の定義は、2つの関数の比率が次のように制限されているx -> infinityことだと思います（ウィキペディアの定義を除算してカットオフポイント|g(x)|を|f(x)|/|g(x)| < constant超えます）。これは、考えるのが簡単な（そして証明するのがより明白な）定義かもしれません。また、BigThetaが対称関係であることも意味します。

これで、「なぜ私が間違っていると思うのか」と尋ねるのに適したツールが手に入りました。次に、数学を使用して、2人のうちどちらが正しいかを判断します。あなたがあなたの主張を証明しなければ、どんな誤解も数学に現れるはずです。

Answer 2

f(n) <= g(n) * 1
2    <= 10^100     for all n >= 0

したがってf(n) = O(g(n))。

f(n) >= g(n) * 2/(10^100)
2    >= 10^100 * 2/(10^100) = 2      for all n >= 0

そしてそうf(n) = Ω(g(n))。

とは両方f(n)=O(g(n))をf(n)=Ω(g(n))意味しf(n) = Θ(g(n))ます。はい、その通りです。