Почему мы предпочитаем не указывать постоянный коэффициент в обозначениях Big-O?

Question

Давайте рассмотрим классическое определение большой O-нотации ( доказательство связи ):

O(f(n)) - это набор всех функций, таких, что существуют положительные константы C и n0 с |g(n)| ≤ C * f(n), для всех n ≥ n_0.

Согласно этому определению допустимо сделать следующее (g1 и g2 - функции, описывающие сложность двух алгоритмов):

g1(n) = 9999 * n^2 + n ∈ O(9999 * n^2)

g2(n) = 5 * n^2 + N ∈ O(5 * n^2)

Также допустимо отметить следующие функции:

g1(n) = 9999 * N^2 + N ∈ O(n^2)

g2(n) = 5 * N^2 + N ∈ O(n^2)

Как видите, первый вариант O(9999*N^2) против (5*N^2) гораздо точнее и дает намчеткое видение, какой алгоритм быстрее.Второй ничего нам не показывает.

Вопрос: почему никто не использует первый вариант?

Answer 1

Использование обозначения O() с самого начала является противоположностью того, чтобы отмечать что-то «точно».Сама идея состоит в том, чтобы замаскировать «точные» различия между алгоритмами, а также возможность игнорировать влияние специфики вычислительного оборудования и выбора компилятора или языка программирования.Действительно, g_1(n) и g_2(n) находятся в одном и том же классе (или множестве) функций n - класса O(n^2).Они отличаются по специфике, но достаточно похожи.

Тот факт, что это класс, - это то, почему я отредактировал ваш вопрос и исправил запись с = O(9999 * N^2) до ∈ O(9999 * N^2).

Кстати - я думаю, ваш вопрос был бы лучшепомещается на cs.stackexchange.com .