漸近複雑度定数、なぜ定数ですか？

Question

Big Oh表記では、すべてのg（n）がいくつかの定数cの要素c.f（n）、O（g（n））であると言います。

私は常に、境界値を得るために境界関数f（n）を乗算するためにこの任意の定数が必要なのかどうか疑問に思っています。

また、この定数をどのようにするべきかを決めるにはどうすればよいですか？

Answer 1

定数自体はg（n）と比較してf（n）の制限動作を特徴付けるものではありません。

これは、そのような定数が存在する場合、あなたは（X）ただし、fはO（gであることを述べることができるよう

こと定数Mの存在を強制数学的定義に使用され（x））、これはアルゴリズムを分析するときの通常の表記法ですが、定数がどれだけ複雑かどうかは気にしません。定数は、それを確実にすることによって、その問題を正しいものにすることができる。M | g（x）|は、f（x）の上限です。

f（x）とg（x）に依存する定数は、f（x）がag（x）big-oを持つことを証明する必要がある数学的な点です。ルール。 thisの例を見てください。

Answer 2

は、それが「早く」g(n) = nとして成長するため、機能

f(n) = 4 * n 

が、それは、この関数を呼び出すO(n)しても意味がありません考えてみましょう。 しかし、Oの定義に一定のものがないと、のようなn0が見つかりません。それはあなたがn0 == 0, c == 4を得ることができますが、一定の必要がある理由だし、実際の条件から、

4 * n <= c * n for all n > n0 

。