little-o

1熱

2答えて

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

-1熱

1答えて

O表記とO表記

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(

0熱

2答えて

アルゴリズム - Little OとBig Omegaは同じ機能を持っていますか？

私は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が厳密な上限になることは保証されますか？

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

0熱

1答えて

シータまたはリトルOの代わりにビッグOを使用する場合

漸近表記についての質問。私は漸近記法の説明の多くは言って見てきた： θ(...)が= 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))もあり