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

Question

В чем разница между обозначением Big-O O(n) и Little-O обозначения o(n)?

Answer 1

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

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

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

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

Для каждого выбора константы k > 0 вы можете найти постоянную a, для которой выполняется неравенство 0 <= f (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 как о <= и о как <)

Answer 2

Биг-О мало-как ≤ это к <, 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.

Answer 3

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

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

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

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

Answer 4

В основном

Асимптотическая запись - это то, что вы можете понять как: как сравниваются функции при уменьшении масштаба?(Хороший способ проверить это - просто использовать такой инструмент, как Desmos, и поиграть колесиком мыши). В частности:

• f(n) ∈ o(n) означает: в какой-то момент, чем больше вы уменьшаете масштаб, тем больше f(n) будет преобладать n (он будет постепенно отклоняться от него).
• g(n) ∈ Θ(n) означает: в какой-то момент уменьшение масштаба не изменит способ g(n) сравнить с n (если убрать галочки с оси, вы не сможете определить уровень масштабирования).

в заключение h(n) ∈ O(n) означает, что функция hможет быть в любой из этих двух категорий. Это может выглядеть какn или он может быть меньше и меньше, чем n когда nувеличивается. По сути, обаf(n) а также g(n) также в O(n).

В информатике

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

Например, если мы докажем, что сложность алгоритма находится в O(n) а также (n) это означает, что его сложность в Θ(n). Это определениеΘи это более или менее переводится как "асимптотически равно". Это также означает, что ни один алгоритм не может решить данную проблему вo(n). Опять же, грубо говоря, "эту проблему нельзя решить менее чем заn шаги ".

Верхняя граница O(n) просто означает, что даже в худшем случае алгоритм завершится не более чем через nшаги (игнорируя все постоянные множители, как мультипликативные, так и аддитивные). Нижняя граница(n) означает, напротив, что мы построили несколько примеров, в которых проблема, решаемая этим алгоритмом, не могла быть решена менее чем за nшаги (снова игнорируя мультипликативные и аддитивные константы). Количество ступеней не болееn и по крайней мере n так что сложность этой задачи "ровно n". Вместо того, чтобы говорить" игнорировать постоянный мультипликативный / аддитивный коэффициент "каждый раз, когда мы просто пишем Θ(n) короче.

Answer 5

У нотации большого O есть компаньон, называемый нотацией малого O. Обозначение большого О говорит, что одна функция является асимптотической. еще один. Сказать, что одна функция асимптотически во-вторых, мы используем строчную нотацию. Разница между обозначениями большого и маленького о аналогична разнице между <= (меньше, чем равно) и <(меньше, чем).