Асимптотическая постоянная сложности, почему постоянная?

Question

Биг-о нотация говорит, что все g (n) являются элементом cf (n), O (g (n)) для некоторой константы c.

Я всегда удивлялся и никогда не понимал, зачем нам нужноэту произвольную константу, умноженную на ограничивающую функцию f (n), чтобы получить наши границы?

Кроме того, как можно решить, каким должно быть число этой константы?

Answer 1

Сама константа не характеризует ограничивающее поведение f (n) по сравнению с g (n).

Используется для математического определения, которое навязывает существование постоянной М такой, что

Если такая константа существует, то вы можете утверждать, что f (x) является O (g (x)), и это обычное обозначение при анализе алгоритмов, вам просто не важно, какая из них константа, а просто сложность самой операции. Константа способна исправить это искажение, гарантируя, что M | g (x) | является верхней границей f (x) .

Как найти, что константа зависит от f (x) и g (x), и это математическая точка, которая должна быть доказана, чтобы гарантировать, что f (x) имеет ag (x) big-o, поэтому нет общего правила , Посмотрите на этот пример.

Answer 2

Рассмотрим функцию

f(n) = 4 * n

Не имеет ли смысла вызывать эту функцию O(n), поскольку она растет "так быстро", как g(n) = n.Но без константы в определении O вы не можете найти n0, например, для всех n > n0, f(n) <= n.Вот почему вам нужна константа, и действительно из условия,

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

вы можете получить n0 == 0, c == 4.