Big-Oh記法について学び始めています。
与えられた関数のC と N 0を見つける簡単な方法は何ですか?
たとえば、次のように言います。
(n+1) 5、または n 5 +5n 4 +10n 2 +5n+1
Big-Oh の正式な定義は次のとおりです。
f(n) と g(n) を、非負の整数を実数にマッピングする関数とします。すべての整数 N > に対して f(n) <= cg(n)となる実定数 c > 0 と整数定数 N 0 >= 1 がある場合、f(n) は O(g(n)) であると言います。 N 0。
私の質問は、c と N 0の値を選択するための優れた確実な方法は何ですか?
(n+1) 5を超える与えられた多項式について、それが O(n 5 ) であることを示さなければなりません。では、推測せずに上記の定義を真にするには、c と N 0をどのように選択すればよいでしょうか?
多項式の各項の係数を追加することで、定数 c を選択できます。以来
| | n 5 + 5n 4 + 0n 3 + 10n 2 + 5n 1 + 1n 0 | <= | n 5 + 5n 5 + 0n 5 + 10n 5 + 5n 5 + 1n 5 |
両側を単純化して取得できます
| | n 5 + 5n 4 + 10n 2 + 5n + 1 | <= | 22n 5 |
したがって、c = 22 であり、これは常に n >= 1 の場合に当てはまります。
N 0を上げることでより低い c を見つけることはほとんどの場合可能ですが、この方法は機能し、頭の中で行うことができます。
(多項式の周りの絶対値演算は、負の係数を考慮します。)
通常、証明はコンクリートCとN0を選択せずに行われます。f（n）<C * g（n）を証明する代わりに、f（n）/ g（n）<Cを証明します。
たとえば、n 3 + nがO（n 3）であることを証明するには、次のようにします。
（n 3 + n）/ n 3 = 1 +（n / n 3）= 1 +（1 / n 2 ）<2 for any n> =1。ここでは、N 0 =1で任意のC>=2を選択できます。。
n->+infitity の場合の lim abs(f(n)/g(n)) が何であるかを確認できます。これにより、定数が得られます (例では g(n) は n^5 であり、f(n) は(n+1)^5)。
x->+infinity の Big-O の意味は、f(x) = O(g(x)) の場合、f(x) は「g(x) より速く成長しない」ということです。 lim abs(f(x)/g(x)) が存在し、+無限大より小さいことを証明します。
検討している機能によって大きく異なります。ただし、関数の特定のクラスについては、アルゴリズムを考え出すことができる場合があります。
たとえば、多項式: C を多項式の先頭の係数より大きい任意の値に設定すると、N 0について解くことができます。
そこの魔法を理解したら、big-O が表記法であることも理解できるはずです。これは、これらの文字の背後で何が起こっているかを理解していれば、解決するすべての問題でこれらの係数を探す必要がないことを意味します。notaionに従って、その規則に従って記号を操作するだけです。
N と c の実際の値を決定する簡単な一般的なルールはありません。それを解くには、微積分の知識を思い出す必要があります。
big-O への定義は limit の定義と絡み合っています。それは c を満足させます:
c > lim |f(n)/g(n)|、n が +infinity に近づくと仮定します。
シーケンスに上限がある場合、常に制限があります。そうでない場合、f は O(g) ではありません。具体的な c を選択した後は、適切な N を見つけるのに問題はありません。