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

Question

В чем разница между Большой-О обозначение O(n) и Маленький-О обозначение 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) < 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) равно true.Вот почему вы можете отбросить константы при работе с нотацией big-O.

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

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

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

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

Следующее справедливо для little-o:

• x2 ∈ o(x3)
• x2 ∈ o(x!)
• ln(x) ∈ o(x)

Обратите внимание, что если f ∈ o (g), то это подразумевает f ∈ O(g).например ,x2 ∈ o (x3) таким образом, также верно, что x2 ∈ O (x3), (опять же, думайте о O как <= и 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!Даже в реальном мире O (N) "лучше", чем O (N2), за исключением глупых вещей вроде сверхмассивных констант и тому подобного.[/ материал, который вы знаете]

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

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