問題タブ [big-theta]

ときどき、途中に何かが入った奇妙な Θ 記号の Θ(n) を見たり、O(n) だけを見たりすることがあります。誰もこの記号を入力する方法を知らないので、単にタイプするのが面倒なのでしょうか、それとも別の意味でしょうか?

関数が属するクラス Big-Theta(g(n)) を示し、アサーションを証明するよう求める演習です。

この場合、f(n) = (n^2+1)^10

定義により、f(n) E Big-Theta(g(n)) <=> c1*g(n) < f(n) < c2*g(n)、c1 と c2 は 2 つの定数です。

この特定の f(n) の Big-Theta が g(n^20) であることは知っていますが、それを適切に証明する人がわかりません。この不等式を操作する必要があると思いますが、方法がわかりません

f(n) が Θ(g(n)) の場合、関数 2 ^f(n)は常に Θ(2 ^g(n) ) ですか? なぜですか、そうでないのですか？

完全な開示：これは宿題の問題です。私は正直なところ、それがとても単純に見えるとき、それが長い間私を回避してきたことを少しおかしく思っています。

さて、質問は、f（n）= n ^ 2 * log（n）、g（n）= n^2.1です。fはtheta（g）に含まれていますか？

特定のn0 、f（n）<= c ₁ g（n）<= c _{2 f（n）を超えるように、定数c 1}、c2を考え出す必要があり_ます。しかし、fがtheta（g）にあるかどうかさえわかりません。私はそれが混乱しています。

MIT コースウェアと CLRS の本、アルゴリズム入門を使って勉強しています。

私は現在再発を解決しようとしています（107ページから）

T(n) = 2T(n/2) + n ⁴

再帰ツリーを作成すると、次のようになります。

レベル 0: n ⁴

レベル 1 2(n/2) ⁴

レベル 2 4(n/4) ⁴

レベル 3 8(n/8) ⁴

ツリーには lg(n) レベルがあります。したがって、再発はあるべきだと思います

T(n) = Θ(n ⁴ lg n)

でもマスター定理を使えばわかる

T(n) = Θ(n ⁴ )

明らかに、これらの両方が正しいとは言えません。どちらが正しいですか？そして、私の推論のどこが間違っていたのでしょうか?

私が理解していることから、1 行目は 1 つの操作、2 行目は(i+1)操作、3 行目は(i-1)操作、4 行目はn操作です。これは、実行時間が になることを意味します1 + (i+1)(i-1) + nか? 私を混乱させるのは、これらの最後のステップだけです。

アルゴリズムの時間複雑度の表現方法を決定する方法は?

またはで時間の複雑さを表現することを選択する必要がありますO(n)かtheta(n)? 関数はまたはf(n)として表現できるためです。Big-Oh(g(n))theta (g(n))

theta よりも big-oh を選択するのはいつですか?

f(n)=n^(logb(n))が入っているTheta(n^k)ために多項式で成長するのか、それともTheta(k^n)指数関数的に成長するのかを理解しようとしています。

f(n) = n^(logb(n)) = n^(log(n)/log(b)) = n^((1/log(b))*log(n))最初に、関数を単純化しようとしまし 1/log(b)たf(n)=n^log(n)。

しかし今、私は立ち往生しています。私の推測では、指数も成長しているため、指数関数f(n)的に、Theta(n^log(n))または超指数関数的log(n)にも成長します。

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

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

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

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

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

このループが O(n^2) であることは知っていますが、Big-Omega と Big-Theta とは何ですか? このような状況で、どのように計算しますか?