Big-O表記法を紹介されたばかりで、いくつか質問があります。ただし、の値を決定する方法については混乱していますn0。3n^3 +20n^2 + 5それがO（n ^ 3）であることを示さなければなりません。これまでのところ：
3n^3 + 20n^2 + 5 <= cn^3
(3 - c)n^3 + 20n^2 + 5 <= 0
5 <= n^3(c - 3) - 20n^2
5 <= n^2(n(c - 3) - 20)
ここからn0とcを見つけるために何をすべきかわかりません。誰か説明してもらえますか？
3n^3 + 20n^2 + 5 <= cn^3
=> 20n^2 + 5 <= cn^3 - 3n^3
=> 20n^2 + 5 <= n^3(c - 3)
=> 20n^2/n^3 + 5/n^3 <= n^3(c - 3)/n^3
=> 20/n + 5/n^3 <= c - 3
=> c >= 20/n + 5/n^3 + 3
大なり記号を開始する場所に応じて、n0を選択して値を見つけることができます。
たとえば、n0 = 1の場合：
c >= 20/1 + 5/1 + 3 which yields c >= 28
Big-O表記の定義により、境界が実際にこれほどタイトである必要はないことに注意してください。これは単純な関数なので、推測して確認することができます（たとえば、cに100を選択し、条件が実際に漸近的に真であることに注意してください）。
例えば：
3n^3 + 20n^2 + 5 <= (5 * 10^40) * n^3 for all n >= 1
真を保持するその不平等は、f（n）がO（n ^ 3）であることを証明するのに十分です。
より良い証明を提供するには、実際には2つの定数が存在し、そのようcにn0存在することを示す必要がありf(n) <= cg(n) for all n > n0ます。
c = 28を使用すると、これを行うのは非常に簡単です。
3n^3 + 20n^2 + 5 <= 28n^3
20n^2 + 5 <= 28n^3 - 3n^3
20n^2 + 5 <= 25n^3
20/n + 5/n^3 <= 25
When n = 1: 20 + 5 <= 25 or 25 <= 25
For any n > 1, 20/n + 5/n^3 < 25, thus for all n > 1 this holds true.
Thus 3n^3 + 20n^2 + 5 <= 28n^3 is true for all n >= 1
（これはかなりひどい「証明」ですが、うまくいけばアイデアが示されます。）
もしあなたが持っていて 、それがどこにあるf(n) = (3n^3 + 20n^2 + 5) かを見たいのなら、私はあなたがn->無限大として 限界をとることができると信じています。O(g(n))g(n) = n^3f(n)/g(n)
3n^3 + 20n^2 + 5制限が3であるため、それは。と同じ速さでしか成長しないことがわかりますn^3。のような多項式がある場合3n^3 + 20n^2 + 5、検査により、最大次数項は常にの値であることがわかりますO(f(n))。
n 0とCを見つけるのはそれほど役に立ちませんが、何かの順序を判断するのは比較的簡単な方法です。他の人がここで言ったように、あなたはただn 0を選んで、それからCを計算することができます。
n 0 = 1を選択すると、が得られ3*(1^3) + 20*1^2 + 5 = 28ます。したがってc1^3 <= 28、cは28でなければなりません。この条件を満たすacとn0があることを示したので、f（n）がO（n ^ 3）であることを証明しました。
3n^3 + 20n^2 + 5 <= cn^3
5 + 20n^2 <= n^3(c - 3)
5/n^3 + 20/n <= c - 3
For n0 = 20, c >= 5, since 5/n^3 + 20/n < 2
n ^ 3で割ると、3 + 20 / n + 5 / n ^ 3 <= C 20 / n + 5 / n ^ 3<=C-3になります。
C値を1020/ n + 5 / n ^ 3<=7とします。
条件が満たされるまで、nのさまざまな値についてこれを解く必要があります。C= 10、n0=3で解が得られます。