Константа разума для Big O

Question

Я немного запутался в том, как определить, когда постоянная важна, чтобы найти большую букву О. Я знаю, что мы должны игнорировать постоянную, чтобы найти большую букву О, но эта функция заставляет меня задуматься дважды:

f(n): 5n + 8n log n + 3 000 000

Я бы подумал, что это O (n log n), но если n начинается с небольших значений, f (n) останется около 3 000 000. Поэтому я должен смотреть на эти типы функций, как если бы n было очень большимзначение?Но если я сделаю это, будет ли это реалистично, поскольку большая часть кода не имеет размера выборки 10 000?

Answer 1

Когда вы вычисляете Big-O для функции, вам всегда нужно думать об очень, очень больших числах. Это помогает вам определить производительность вашей функции, когда размер выборки становится бесконечным (другими словами, когда он становится очень очень большим).

Обычно, после того, как вы вычислите Big-O, вы также захотите найти число n0. Вы можете думать об этом n0 числе как переломный момент . Производительность функции с любым числом больше n0 будет равна Big-O. Для меньших чисел производительность будет зависеть от констант или других факторов в функции. Вот почему одного Big-O недостаточно для оценки производительности функции (, хотя это первое, что вы должны определить ). После того, как вы определили Big-O, вы должны протестировать или определить время своей функции, определить точку опрокидывания n0 и определить, какие размеры выборки или количество элементов будет обрабатывать ваша функция большую часть времени.

Иногда вы будете писать функции, которые будут работать с относительно небольшими наборами чисел (скажем, 10 с или 100 с), и иногда ваши функции будут обрабатывать элементы порядка миллионов или миллиардов.

Answer 2

Большая O-нотация используется для определения ограничивающего поведения при увеличении аргумента до бесконечности. Вот почему вы игнорируете константу: она затопляется, когда n становится все больше и больше.

Ознакомьтесь с ответами (в частности, с самым высоким баллом) на на этот вопрос для получения более подробной информации.

Но вы столкнулись с одним из ограничений бездумного следования Большому О: всегда есть другие соображения. Ваша константа на самом деле может быть довольно большой (как в вашем случае), а ваши значения n всегда будут маленькими (как в вашем случае), поэтому эффективный алгоритм равен O(1). Однако, технически говоря, это O(n log n), потому что вы должны игнорировать константу.

Answer 3

Вы должны учитывать константу, когда ваш размер данных / ввод невелик. Но поскольку при разработке этих алгоритмов верхняя граница не учитывается, константы игнорируются.

Например:

Оба: сортировка слиянием и быстрая сортировка nlogn. Но быстрая сортировка имеет небольшой постоянный коэффициент, поэтому при небольших входных данных она ведет себя быстрее, чем сортировка слиянием.