Big-O の非公式な考え方は、「関数の成長の最高次数」、つまり f(n) = 3n^2 + 5n + 50 は O(n^2) であると説明されています。
Big-O が「この期間より悪化しないことが保証されている」という言い方であることは理解しています。正式には、定義は f(n) -> O(g(n)) iff f(n) <= c * g(n) で、c は正のようです。
最初にいくつかの数学的なもの.. if f(n) = 5n^2, g(n)=n
5n^2 <= cn
5n <= c
c が定数ではないという考え (それが要件かどうかはわかりません) であり、それが f(n) が O(g(n)) にないという証拠である場合、g(n) がn^3 (そのうち必ず含まれているはず)?
5n^2 <= cn^3
5/n <= c
私が想定しているこれらすべてに対して数学がどのように機能するかについて誤解があるので、私は尋ねます：
この派手なものはどのように機能しますか
私のデータ構造クラスで与えられた単純な定義にどのように接続しますか?
助けてくれてありがとう
nは正の整数であり1<=n、したがって5/n<=5/1=5を選択できるため、 を選択できますc=5。
より完全な定義では、n0と、両方の定数を選択して、すべてに対してaのみ証明することもできます。f(n)<=a+c*g(n)n0<n
Big-O の非公式な考え方は、「関数の成長の最高次数」、つまり f(n) = 3n^2 + 5n + 50 は O(n^2) であると説明されています。
これが Big-O の背後にあるアイデアだとは言えません。非公式に Big-O とは、特定の関数が超えることができないものを大まかに見積もったものです。そして、その使用法は主に、何かが大きな数でどのように成長するかを近似しています。
たとえば、6 桁の数字の場合、桁を調べなくても 100 万未満であると断言できます。これで十分な場合が多く、すべての桁を分析する必要はありません。
機能の成長を分析するために、2 つの要因が役割を果たします。
fよりも大きい場合、大きな定数gを掛けることで修正できます。これは、の利点が成長によるものではないことを意味しますgfこれは、定義の 2 つの部分につながります: (1) 何らかの定数と (2) 十分な大きさの n
実際、多項式の場合、高次成分が成長速度を定義します。