Ответ 1
f ∈ O (g) говорит, по существу,
Для по крайней мере одного выбора константы k > 0 вы можете найти константу a такую, что неравенство 0 <= f (x) <= kg (x) выполняется для всех х > а.
Заметим, что O (g) - множество всех функций, для которых выполняется это условие.
f ∈ o (g) говорит, по существу,
Для каждого выбора константы k > 0 вы можете найти константу a такую, что неравенство 0 <= f (x) < k g (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) истинно. Вот почему вы можете сбросить константы при работе с нотами с большими выводами.
Однако, если f ∈ o (g) истинно, то g должна включать в свою форму более высокую степень x, и поэтому относительное разделение между f (x) и g (x) должно фактически увеличиваться по мере x становится больше.
Использовать чисто математические примеры (а не ссылаться на алгоритмы):
Для Big-O верны следующие значения, но это не так, если вы использовали little-o:
- x ^ 2 ∈ O (x ^ 2)
- x ^ 2 ∈ O (x ^ 2 + x)
- x ^ 2 ∈ O (200 * x ^ 2)
Для little-o верно следующее:
- x ^ 2 ∈ o (x ^ 3)
- x ^ 2 ∈ o (x!)
- ln (x) ∈ o (x)
Заметим, что если f ∈ o (g), то это означает, что f ∈ O (g). например x ^ 2 ∈ o (x ^ 3), то также верно, что x ^ 2 ∈ O (x ^ 3) (опять-таки, полагаем O как <=
и o как <
)