little-o

    0

    2答えて

    私はf(n),g(n)という2つの機能を持っています。f(n)=o(g(n))です。 を明確にするために、私はそれはf(n)=Omega(g(n))ことを、私に与えられ、その情報を持つことも可能である oを少しについて取っています。 私にはほとんど-Oの定義は for every c>0,f(n)<c * g(n). おかげと私に言っているので、それは、それは可能ではないということですね!

    0

    1答えて

    little-oがタイトな上限か厳密な上限かどうか?間違った場合 は、以下の答えを修正し、 g(x)は漸近的にタイトではないことf(x)の上限です。 の場合、f ∈ o(g)の場合は、f ∈ O(g)よりもはるかに大きなギャップがあります。 ビッグオーグはリトルオフであるから、≦<である。 big-Oは包括的な上限ですが、little-oは厳密な上限です。 厳密な上限を保証するだけでは不十分ですか

    0

    1答えて

    漸近表記についての質問。私は漸近記法の説明の多くは言って見てきた: θ(...)が= O(...)に似ていることは<= o(...)に類似していることを意味すると思われる< に似ていますf(n) = O(g(n))の場合、f(n) = θ(g(n))またはf(n) = o(g(n))のいずれかです。 f(n) = O(g(n))には、f(n) = θ(g(n))もf(n) = o(g(n))もあり

    1

    2答えて

    私は大量のデータセットを持つアルゴリズムのコースでこの課題に座っていますが、Little-Oh表記を使用すると混乱します。ビッグオフには完全に自信があります。 私は課題への解決を望んでいないので、提示しません。代わりに私の質問は、時間の複雑さをどのように解釈するのですかo(log n)? 私はアルゴリズムAがo(log n)よりも漸近的に遅くなる必要があることを知っていますが、これはアルゴリズムが

    -1

    1答えて

    f(n) = Θ(g(n))は、私はf(n) = O(n)とf(n) = Ω(g(n))を知っている場合、私は全てのn> N1ため、c1*g(n) ≤ f(n) ≤ c2*g(n)が存在し、c1とc2≥0、N1≥0が存在しなければならないと言うことになります。 いくつかのc> 0の場合、f(n) = c*g(n) + o(g(n))となります。私のポイントはf(n) ≤ c2*g(n) ==>f(