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

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) истинно. Вот почему вы можете опускать константы при работе с нотацией большого 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 как о <)

Big-O для маленького, как ≤ для <. 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.

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

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

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

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

В целом

Асимптотическую нотацию можно понять так: как функции сравниваются при уменьшении масштаба? (Хороший способ проверить это - просто использовать такой инструмент, как 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).

Пример с min(array)

Представьте, что нам нужен алгоритм, который находит минимальное значение в массиве размером n. Нижняя граница этой проблемы равна o(n), потому что ни один алгоритм не может вычислить min, не прочитав каждый элемент хотя бы один раз (если есть хотя бы один элемент, который алгоритм не может прочитать тогда, неизвестное значение может быть или не быть минимальным. алгоритм не может дать правильный результат в обоих этих неотличимых сценариях). С другой стороны, очень легко представить алгоритм O(n), который решает min (читать каждый элемент и сохранять текущее минимальное значение). Когда мы знаем и min ∈ o(n), и min ∈ O(n), мы можем сказать, что min ∈ Θ(n).

У нотации большого O есть компаньон, называемый нотацией маленького O. Обозначение большого О говорит, что одна функция является асимптотической no more than другой. Чтобы сказать, что одна функция асимптотически less than является другой, мы используем строчную нотацию. Разница между обозначениями большого и малого O аналогична разнице между ‹= (меньше чем равно) и‹ (меньше чем).