Разница между обозначениями Big-O и Little-O

Ответы:

444

f ∈ O (g) говорит, по существу,

По крайней мере, для одного выбора константы k > 0 можно найти постоянную a , для которой выполняется неравенство 0 <= f (x) <= kg (x) для всех x> a.

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

f ∈ o (g) говорит, по существу,

Для каждого выбора константы k > 0 вы можете найти постоянную a , для которой выполняется неравенство 0 <= f (x) <kg (x) для всех x> a.

Еще раз отметим, что o (g) является множеством.

В Big-O необходимо лишь найти конкретный множитель k, для которого неравенство выходит за пределы некоторого минимума x .

В Little-o должно быть, что существует минимум x, после которого выполняется неравенство, независимо от того, насколько малым является k , если оно не отрицательно или равно нулю.

Они оба описывают верхние границы, хотя несколько нелогично, Little-o - более сильное утверждение. Существует намного больший разрыв между скоростями роста f и g, если f ∈ o (g), чем если f ∈ O (g).

Одна иллюстрация несоответствия такова: f ∈ O (f) верно, а f ∈ o (f) неверно. Следовательно, Big-O можно прочитать как «f ∈ O (g) означает, что асимптотический рост f не быстрее g», тогда как «f ∈ o (g) означает, что асимптотический рост f строго медленнее, чем g». Это как <=против <.

Более конкретно, если значение g (x) является постоянным кратным значения f (x), то f ∈ O (g) является истинным. Вот почему вы можете отбрасывать константы при работе с нотацией big-O.

Однако, чтобы f ∈ o (g) было истинным, тогда g должен включать более высокую степень x в свою формулу, и поэтому относительное разделение между f (x) и g (x) должно фактически увеличиваться с увеличением x.

Чтобы использовать чисто математические примеры (вместо ссылок на алгоритмы):

Следующее верно для Big-O, но не будет верно, если вы использовали little-o:

  • x² ∈ O (x²)
  • x² ∈ O (x² + x)
  • x² ∈ O (200 * x²)

Следующее верно для little-o:

  • x² ∈ o (x³)
  • x² ∈ o (x!)
  • ln (x) ∈ o (x)

Отметим, что если f ∈ o (g), то это означает f ∈ O (g). например, x² ∈ o (x³), поэтому также верно, что x² ∈ O (x³), (опять же, представьте O как <=o и o как <)

Тайлер МакГенри
источник
146
Да, разница в том, могут ли две функции быть асимптотически одинаковыми. Интуитивно мне нравится думать о значении big-O «растет не быстрее, чем» (то есть растет с той же скоростью или медленнее), а значение little-o «растет строго медленнее, чем».
Фил
12
Скопировать это в Википедию? Это намного лучше, чем там.
cloudsurfin
1
@ СА Да. Это более сложный случай, когда простое правило, которое я дал о «высших степенях х», явно не применимо. Но если вы посмотрите на более строгие определения пределов, приведенные в ответе Стриланка ниже, вы должны знать, что lim n-> inf (2 ^ n / 3 ^ n) = 0. Так как (2 ^ n / 3 ^ n) = (2/3) ^ n, и поскольку для любого 0 <= x <1, lim n-> inf (x ^ n) = 0 верно, что 2 ^ n = o (3 ^ n).
Тайлер МакГенри
1
Будьте осторожны с «В Литтл-о, должно быть, что есть минимум х, после которого неравенство сохраняется независимо от того, как мало вы делаете k, до тех пор, пока оно не будет отрицательным или нулевым». Это не "для каждого, aчто есть k: ...", это "для каждого, kчто есть a: ..."
GA1
1
«В Литтл-о, должно быть, есть минимум х, после которого неравенство сохраняется независимо от того, как мало ты делаешь k, до тех пор, пока оно не будет отрицательным или нулевым» нет, это неверно
Филиппо Коста
196

Биг-О - это мало-о, как ≤есть <. Big-O - это включающая верхняя граница, в то время как little-o - строгая верхняя граница.

Например, функция f(n) = 3n:

  • в O(n²), o(n²)иO(n)
  • не O(lg n), o(lg n)илиo(n)

Аналогично, номер 1:

  • ≤ 2, < 2И≤ 1
  • не ≤ 0, < 0или< 1

Вот таблица, показывающая общую идею:

Большой стол

(Примечание: таблица является хорошим ориентиром, но ее определение предела должно быть в терминах верхнего предела, а не нормального предела. Например, 3 + (n mod 2) колеблется между 3 и 4 навсегда. Это O(1)несмотря на отсутствие нормального предела, потому что оно все еще имеет а lim sup: 4.)

Я рекомендую запомнить, как нотация Big-O преобразуется в асимптотические сравнения. Сравнения легче запомнить, но они менее гибкие, потому что вы не можете говорить такие вещи, как n O (1) = P.

Крейг Гидни
источник
У меня один вопрос: в чем разница между строкой 3 и 4 (столбец определения пределов)? Не могли бы вы показать мне один пример, где 4 содержит (lim> 0), но не 3?
Человек в маске
3
О, я понял это. Big Omega для lim> 0, Big Oh для lim <бесконечность, Big Theta, когда оба условия выполняются, что означает 0 <lim <бесконечность.
Человек в маске
Для f ∈ Ω (g) не должен ли предел на бесконечности принимать значение> = 1? Аналогично для f ∈ O (g) 1 = <c <∞?
user2963623
1
@ user2963623 Нет, поскольку конечные значения строго выше 0, включая значения от 0 до 1, соответствуют «одинаковой асимптотической сложности, но различным постоянным коэффициентам». Если вы опустите значения ниже 1, вы получите отсечение в пространстве с постоянным множителем, а не в пространстве с асимптотической сложностью.
Крейг Джидни
1
@ubadub Вы транслируете операцию возведения в степень по набору. Это беспорядочная запись.
Крейг Гидни
45

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

[материал, который вы знаете] Распространенный способ классификации алгоритмов - по времени выполнения, и, сославшись на сложность алгоритма с большим числом ой, вы можете получить довольно хорошую оценку того, какой из них «лучше» - какой из них имеет «наименьшую» функцию в О! Даже в реальном мире O (N) «лучше», чем O (N²), за исключением глупых вещей, таких как сверхмассивные константы и тому подобное. [/ Материал, который вы знаете]

Допустим, есть некоторый алгоритм, который работает в O (N). Довольно хорошо, а? Но допустим, что вы (вы, гениальный человек) придумали алгоритм, который работает в O ( N ⁄ loglogloglogN ). УРА! Это быстрее! Но вы будете чувствовать глупость писать это снова и снова, когда пишете свою диссертацию. Итак, вы пишете это один раз и можете сказать: «В этой статье я доказал, что алгоритм X, ранее вычисляемый за время O (N), фактически вычислим в o (n)».

Таким образом, все знают, что ваш алгоритм быстрее - насколько непонятно, но они знают, что он быстрее. Теоретически. :)

agorenst
источник