証明が解けなくて困っています。ここで、t(n) <= cn^1.6、c は定数です。一般に、Big Omega は Big O とは逆で、最良のシナリオであり、下限を探します。したがって、n >= n0 となる ac と n0 が存在します。しかし、これを証明に適用する方法と、方程式の定数を操作して c と n0 を見つけ、t(n) が Omega(n^1.6) であることを証明する方法がわかりません。
t(n) = (n-3logn)^1.6 + 5n^1.5 + 7はオメガ(n^1.6)
この種の問題を解決する方法について、誰かが洞察を提供できますか? 前もって感謝します！
また、私の下のコメントから受け取ったような批判は受けません。これは宿題の問題ではなく、このタイプの問題の背後にある一般的な概念を誰かが簡単に説明できるように、一連の演習から取った例です。
Big-Omega の定義: f(n)=Omega(g(n)) すべての n > K に対して、f(n) > C * g(n) となる定数 C および K が存在する場合
言い換えれば、次のように言える必要があります。
今あなたの問題を見てみましょう。
t(n) = (n-3logn)^1.6 + 5n^1.5 + 7 is Omega(n^1.6)
C * n^1.6 < (n-3logn)^1.6 + 5n^1.5 + 7
n^1.6 で割る
C < ((n-3logn)/n)^1.6 + 5n^-0.1 + 7/n^1.6
C < (1 - 3logn/n)^1.6 + 5n^-0.1 + 7/n^1.6
それでは、これら 3 つの用語を 1 つずつ見ていきましょう (もちろん、より正式な証明が必要になりますが、これらは簡単です)。
1. (1 - 3logn/n)^1.6 = (1 - 0.smth)^1.6 = (0.smth)^1.6 < 1 for n > 2
2. 5n^-0.1 = 5/n^0.1 = 5/smth greater than 1 < 5 for n > 2
3. 7/n^1.6 = 7/smth large < 1 for n > 2
したがって、任意の n > 2 について、C < 1 + 5 + 1 = 7 であることがわかります。
ここで、「私は C=7 を選択し、任意の n > 2 に対して、C*n^1.6 < ...」と言うことができます。