Big-O, когда значение n становится очень маленьким?

Question

Я пропустил класс, где был представлен big-O, думая, что это было довольно просто. Тем не менее, кажется, что учитель что-то говорил об отклонении O (n) от функции, когда n становится очень маленьким? Я не мог найти это нигде в книге. Может ли кто-нибудь просветить меня? Наше исследование O (n) было в контексте алгоритмов сортировки, если это имеет какое-либо значение.

Спасибо Гена

редактировать: Спасибо за помощь, ребята, это освещает. У меня есть дополнительный вопрос. Есть ли относительно простой математический способ выяснить точку, где n слишком мало для O (n)?

Похожие вопросы

существуют ли алгоритмы O (1 / n)?
В чем разница между Θ (n) и O (n)?

Answer 1

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

Вот почему, в общем, для небольших множеств большое значение O не имеет значения. Для большинства объектов с простыми сравнениями быстрая сортировка по 10 элементам не будет заметно быстрее, чем пузырьковая сортировка, линейный поиск по 100 элементам, вероятно, будет быстрее, чем двоичное дерево, и т. Д.

Answer 2

Концепция обозначения Big-O заключается в асимптотической эффективности алгоритма. Когда N становится больше, термин в обозначении Big-O начинает доминировать над общим временем. Например, в алгоритме O (N ^ 2) общее время T (N) может быть:

T(N) = a * N * N + b * N + c

По мере того, как N становится все больше и больше, член в N ^ 2 доминирует независимо от значения b или c.

Когда N мало, термины b и c имеют значение.

Например, если a = 0,001, b = 1 000 и c = 1 000 000.

 N                ~ T(N) [1 significant figure]
 1                1,000,000                (almost all c)
 1,000            2,000,000                (50:50 split on b and c)
 1,000,000        2,000,000,000            (50:50 split on a and b)
 1,000,000,000    1,000,000,000,000,000    (almost all a)

Итак, если вы проигнорируете младшие члены, производительность при низком N будет полностью искажена. При высоком N младшие члены не имеют значения.

Answer 3

Материал курса становится все труднее понять, так как количество посещаемых лекций (N) становится очень маленьким.

Answer 4

Может быть, ниже приведен пример "O (n) отклонения от функции, когда n становится очень маленьким":

Рассмотрим операцию, которая требует, например, времени «50 умноженных на n плюс n в квадрате».

Когда n большое, тогда будет доминировать термин «n в квадрате», и поэтому можно сказать, что операция «O (n в квадрате)».

Однако, когда n мало, термин "n в квадрате" будет пренебрежимо мал, и термин "50 умножить на n" будет доминировать, и поэтому, когда (и только когда) n мало, тогда можно сказать, что оно равно O (п).

Answer 5

Чтобы расширить ответ выше, нотация Big-Oh измеряет возможный рост функции или ее ограничивающее поведение.

f = O (g), если и только существует N и константа c (которая может быть функцией N) такой, что для всех n> N,
f (n) <= c * g (n) </p>

Допустим, f = 10000000 * n и g = n ^ 2.

f = O (g), однако, если вы посмотрите на слишком малые значения n, скажем, менее 10000000 и установить с = 1, вы увидите, что g (n) <= f (n). </p>

---

Чтобы добавить более экстремальный пример, вы бы предпочли иметь дело с алгоритмом с сложность n ^ 100000 или алгоритм со сложностью 2 ^ (. 0000000001n). За разумные размеры проблемы, последний лучше. Что делает много CS настолько красива, что допускает такого рода злоупотребления, однако, наиболее естественным алгоритмы не пользуются этим преимуществом. Большинство алгоритмов полиномиального времени имеют небольшие константы (по крайней мере, после небольшой работы).

Удачи!

Answer 6

Согласно определению:
f (n) = Θ (g (n)) означает набор всех функций f (n) , так что должны быть постоянные c1 и c2 и также n0 , где все эти случаи true :

• c1. g (n) - неотрицательный термин или 0.
• c1. g (n) <= f (n) </em> [g (n) должна быть нижней границей для определенного n]
• f (n) <= c2. g (n) </em> [g (n) также должен быть верхней границей, поскольку мы определяем Θ].
• для всех n больше, чем выбранное нами n0

Таким образом, все, что нам нужно сделать, это выбрать такие c1, c2 и n0, которые делают ВСЕ условия истинными. Поэтому для определенных комбинаций c1 c2, если вы выберете n

Answer 7

Большой не по теме, но ради полноты я хочу упомянуть некоторые другие нотации, которые связаны с нотацией Big_o и обычно используются в теоретической информатике и которые вы можете найти в литературе по информатике: Big-- обозначение, обозначение Big-Ω и обозначение little-o. Это просто другие (и более жесткие) описания темпов роста. Обозначение little-o легко принять за обозначение big-O.

Little-o также является отношением между двумя функциями f (x) и g (x). Сказать, что «f (x) мало-мальски g (x)» означает, что f (x) растет намного быстрее, чем g (x). В более математических словах говорится, что предел f (x) / g (x) равен нулю, когда x приближается к бесконечности.

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

См. Страницу Big-o википедии , где можно получить краткое и краткое представление различных обозначений.