Prove 5n^2 + 2n -1 = O（n^2）です。 これは私がこれまで試みられてきたものである：Big O表記の証明
5n^2 + 2n -1 <= 5n^2 + 2n^2 -n2 for n>1
5n^2+ 2n -1 <= 6n^2 for n>1
5n^2+ 2n -1 = O(n^2) [ c = 6n^2, n0 = 1 ]
これはランダウの記号を証明する正しい方法ですか？
これはうまく見えますが、割り当て作業やその他の正式な作業のためにそれをやっている場合は、fなどの定数（c）の値を選択するなど、より正式な方法で行うこともできます（n）/ g（n）。それ以外は正しいように見える。
あなたの表現がO(n^2)であることを証明するために、あなたはそれはいくつかの定数Mといくつかの最小値nため、M*n^2で囲まれていることを示す必要があります。 n = 10について
：検査によって、私たちはあなたの式がn=10ため、10*n^2で囲まれていることを示すことができる
5n^2 + 2n -1 <= 10*n^2
500 + 20 - 1 <= 1000
519 <= 1000
は、我々はまた、式が任意の値のため10*n^2によって制限されることを示すことができるよりもn大きいです10：n > 10については
：
5n^2 + 2n -1 <= 10*n^2
5*(10+i)^2 + 2*(10+i) -1 <= 10*(10+i)^2
5*(i^2 + 20i + 100) + 2i + 19 <= 10*(i^2 + 20i + 100)
2i + 19 <= 5*(i^2 + 20i + 100)
2i + 19 <= 5i^2 + 100i + 500
5i^2 + 98i + 481 >= 0, which is true for `i > 0`
はビッグO記法上のWikipediaの記事へのリンクです：
https://en.m.wikipedia.org/wiki/Big_O_notation
更新：
注実際には、あなたの表現O(n^2)を標識するために、我々は」勝ったことそのような醜い書かれた証拠に頼ることはありません。代わりに、我々はn^2という用語が大きなnの表現を支配し、全体的な振る舞いがO(n^2)であることを認識するだけです。あなたの表現はO(n^3)（そしてO(n^4)など）です。
したがって、n = 10の場合はn ** 3に限定されるので、書くのにはあまり役に立ちませんが、 'O（n ** 3）'でもあります。 –
@EricDuminilはいそれは 'O（n^3）'でもありますが、通常、人々は可能な限り最小限の束縛を得ようとします。あなたが2カ月以内に洗濯をすることができることをあなたに教えてください。実際には機能的に役に立たないのですが、週末までに洗濯が必要なためです。 –
:)あなたはまったく正しいです。それは、彼はまたコメントでそれを証明する必要があることをOPが言及しただけです。 –
我々は、（n）はF = 5×N^2 + 2 * N-1及びG（N）=たN F（n）を証明するために^ 2
= O（G（N） ）、2つの定数、すなわちc> 0とn_0、st f（n）< =すべてのn> = n0に対してc.g（n）。
c = 5.5という値を選択しましょう。 f（n）とc * g（n）を評価してプロットしましょう。このプロットから分かるように、理論的にはn^2/2 * 2 * n + 1 =（n^2-4 * n + 2）/ 2 =（（n-2）^ 2）全てのn> = n0 = 4に対して5 * n^2 + 2 * n-1 < = 5.5 * n^2を意味する。したがって、f（n） = O（g（n））である。 （証明）
最初の行は不要である（実際に修正していない） – Henry
大感謝を！もう1つの質問は、5n^2 + 2n -1 = O（n^3）を証明すると言う - それは偽になるでしょうか？ –
6n^2ではなく、c = 6であることに注意してください。 – BlackBear