2 つの漸近関数の証明に出くわしました。
f(n) = O(g(n)) は 2^f(n) = O(2^g(n)) を意味します
Given: f(n) ≤ C1 g(n)
So, 2^f(n) ≤ 2^C1 g(n) --(i)
Now, 2^f(n) = O(2^g(n)) → 2^f(n) ≤ C2 2^g(n) --(ii)
From,(i) we find that (ii) will be true.
Hence 2^f(n) = O(2^g(n)) is TRUE.
この証明が正しいかどうか教えていただけますか? これを解決する他の方法はありますか？
2.f(n) = O((f(n))^2)
2番目の例をどのように証明しますか? ここで、f(n)<1 の場合と f(n)>1 の場合の 2 つのケースを考えます。
Note: None of them are homework questions.
例 1 の試みられた証明は善意に見えますが、欠陥があります。まず、「<code>2^f(n) ≤ 2^C1 g(n)」は を意味します2^f(n) ≤ (2^C1)*g(n)が、これは一般に誤りです。書かれているはずです2^f(n) ≤ 2^(C1*g(n))。「Now」で始まる行では、明示的に言う必要がありますC2 = 2^C1。「(ii) が真になる」という主張は空虚です ((ii) はありません)。
f(n) = 1/nすべての n > N に対して f(n) < C*(f(n))² となるような定数 N と C は存在しないため、関数 likeは例 2 の主張を反証します。証明: いくつかの N と C が与えられているとします。n>N、n>C を選択します。f(n) = 1/n = n*(1/n²) > C*(1/n²) = C*(f(n))²。N と C は任意に選択されたので、これは、すべての n > N に対して f(n) < C*(f(n))²、QED となるような N と C の固定値がないことを示しています。
「f(n) ≥ 1」と言うだけでは、2 番目の主張を証明するのに十分ではありません。しかし、「すべての n について f(n) ≥ 1」または「f() ≥ 1」と書けば、証明可能です。たとえば、f(n) = 奇数 n の場合は 1/n、偶数 n の場合は 1+n の場合、偶数 n > 0 の場合は f(n) > 1、奇数 n の場合は 1 未満になります。f(n) = O((f(n))²) が偽であることを証明するには、前の段落と同じ証明を使用しますが、n が偶数であるという追加条件を使用します。
実際、「すべての n について f(n) ≥ 1」は、f(n) = O((f(n))²) を保証するために必要以上に強力です。ε を任意の正の固定値とします。ε がどんなに小さくても、「すべての n > N' に対して f(n) ≥ ε」により、f(n) = O((f(n))²) が保証されます。これを証明するには、C = max(1, 1/ε) と N=N' を取ります。