宿題の質問があります
Given f(n) is O(k(n)) and g(n) is O(k(n)), prove f(n)+g(n) is also O(k(n))
どこから始めればよいかわかりません。これに取り組む方法を教えてくれる助けはありますか?
質問する
378 次
3 に答える
0
Big-Oh表記の規則を参照してください。
合計ルール：f(n) isO(h(n))とg(n)isの場合O(p(n))、f(n)+g(n)isはO(h(n)+p(n))。
このルールをケースに使用すると、複雑さはになります。O(2k(n))これはに他なりませんO(k(n))。
于 2012-06-21T12:58:01.003 に答える
0
したがって、f(n) は O(g(n)) であり、f(n) は、n の任意の大きな値に対して g(n) の正の定数の倍数以下である (つまり、f(n) <= cg(n) for n >= n_0)。通常、何かが O(g(n)) であることを証明するには、c と n_0 を提供して、それが真であることを示します。
あなたの場合、その定義を使用することから始めるので、f(n) <= ck(n) および g(n) <= dk(n) と言えます。質問に完全に答えるつもりはありませんが、基本的には f(n)+g(n) <= tk(n) を示そうとしているだけです。
*c、d、および t はすべて任意の正の定数です。さらにヘルプが必要な場合は、コメントしてください。喜んで詳細情報を提供します。
于 2012-06-21T17:24:46.373 に答える
0
論理的にそれを試してみてください。 f(n)直線的に増加します。そうg(n)です。したがって
O(n) + O(n) = O(2n)
関数のビッグ O 分類を見つけようとすると、定数はカウントされません。残りの部分 (理由を含む) は演習として残しておきます。（SOで完全な答えを得ることは不正行為です！）
于 2012-06-21T12:48:23.387 に答える