直観は f ∈ O(g) であり、g が何らかの形で f と等しいか、または大きいことを意味します。f ∈ Ω(g) は、g が何らかの形で f に等しいか、または小さいことを意味します。私の答えでは、定数の選択方法についてあまり正確/うるさいことはしません。
まずウォーミングアップとして、次のことを自分自身に納得させる必要があります
- f ∈ O(f) および f ∈ Ω(f)。(定義で c=1、k=1 とする)。
- f ∈ O(g) の場合、g ∈ Ω(f) であり、その逆も成り立ちます。(一方に定数 (c,k) が見つかった場合、(1/c, k) はもう一方に必要な定数です)
- f ∈ O(g) の場合、任意の正の定数 P,Q に対して f ∈ O(P*g) および Q*f ∈ O(g) です。これは、関数に正の定数を掛けても問題ないことを意味します。Ωも同様。
- f ∈ O(g) かつ f ∈ O(h) の場合、f ∈ O(MIN(g,h)) です。
- f ∈ Ω(g) かつ f ∈ Ω(h) の場合、f ∈ Ω(MAX(g,h)) です。
f+g の O または Ω を見つけようとする場合、通常は O(f) または O(g) または Ω(f) または Ω(g) を推測します。
3^n + n^4 の場合、3^n ∈ O(3^n)、n^4 ∈ O(n^4)、および 3^n + n^4 ∈ O(3^n) がわかっています。 + n^4)。しかし、私たちはもっとうまくやりたいと思っています。3^n + n^4 ∈ O(3^n + 3^n) = O(3^n) を証明したい。n^4 ∈ O(3^n) を示すことができれば、これを行うことができます。
定義が行うべきことを正確に行う必要があります: すべての n>k に対して (c,k) が存在することを示します。
n^4 ≤ c3^n
4log(n) ≤ log(c) + nlog(3)
4log(n) - nlog(3) ≤ log(c)
この c が常に存在することを示す 1 つの方法は、微積分を使用することです。4log(n) - nlog(3) が最終的に減少する関数であることを示します。導関数は 4/n - log(3) であり、n が十分に大きい場合は負であることがわかります。したがって、n が十分に大きい場合、4log(n) -nlog(3) は減少します。したがって、不等式が真である正の定数 c があります。したがって、n^4 ∈ O(3^n) です。そして、3^n + n^4 ∈ O(3^n + 3^n) = O(3^n) です。
3^n + n^4 ≥ 1*3^n なので、3^n + n^4 ∈ Ω(3^n) です。定数が問題ではないことを示すために、c_1*3^n + c_2*n^4 という c_1 と c_2 を使用してみましょう。d := min(c_1, c_2) とする。それで
c_1*3^n + c_2*n^4 ≥ d(3^n + n^4) ≥ d*3^n
したがって、c_1*3^n + c_2*n^4 ∈ Ω(3^n) です。同様に、O(3^n) の場合: d := max(c_1, c2) とします。次に、n が十分に大きい場合、
c_1*3^n + c_2*n^4 ≤ d(3^n + n^4) ≤ d(c*3^n) = (dc)*3^n
3^n + n^4 ∈ O(3^n) であるため、この c が存在することがわかります。したがって、c_1*3^n + c_2*n^4 ∈ O(3^n) です。
十分に答えたかどうかはわかりませんが、役に立てば幸いです。