Математика, лежащая в основе «большого О» и других асимптотических обозначений

Формальные определения таких обозначений, как «Big O», «Big Omega» и «Big Theta».

Big O (произносится как «big oh») - математическое обозначение, широко используемое в информатике для описания эффективности алгоритмов с точки зрения вычислительного времени или объема памяти. Основная цель этой и других так называемых асимптотических обозначений - описать поведение математических функций путем сравнения их «порядков роста».

В этой статье я сначала дам краткий обзор того, как нотация Big O используется на практике для описания эффективности алгоритмов. Позже я представлю его математическое определение, а также определения других подобных обозначений, таких как «Большая Омега» (Ω) и «Большая Тета» (Θ). Кроме того, я также предлагаю несколько формальных методов, которые вы можете использовать для классификации математических функций в соответствии с этими определениями.

«Big O» в двух словах

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

Обозначение Big O обычно используется для распределения алгоритмов по нескольким базовым классам эффективности, например O (log (n)), O (n) , O (n * log (n)), O (n²) и т. д. Мы говорим, что стандартный алгоритм линейного поиска работает за O (n), потому что ожидается, что время его выполнения будет линейно увеличиваться с размером входных данных. Точно так же мы знаем, что двоичный поиск составляет O (log (n)), а наиболее эффективные алгоритмы сортировки могут выполняться за O (n * log (n)) .

Однако утверждение, что алгоритм является O (n²), не означает, что он выполняет ровно n² операций для заданного ввода размера n. Представьте, что алгоритм A всегда выполняет f (n) = 2n² + n + 1 операций. Что люди обычно делают с этой функцией, так это отбрасывают ее недоминантные термины (например, + n и + 1) и ее константы (например, 2 в 2n²), чтобы получить его асимптотическое обозначение O (n²). Если существует алгоритм B, который всегда выполняет f (n) = 4n² + 3n + 3 операций, его также можно описать как O (n²), хотя он выполняет больше чем в два раза больше операций, чем алгоритм A для любого значения n.

Но в этом нет ничего плохого. Когда мы используем асимптотические обозначения, такие как Big O, мы заинтересованы в сравнении порядков роста, вместо того, чтобы заботиться о точных числах. Основная цель этого анализа - описать, как время выполнения или объем памяти, требуемый алгоритмом, увеличивается в зависимости от входного размера n, особенно когда n значительно велик.

Если алгоритм O (n²),, это означает, что если мы удвоим размер ввода, то количество выполняемых операций будет примерно в четыре раза. При увеличении n = 100 до n = 200 количество операций, выполняемых алгоритмом A, увеличится с 20 101 до 80 201 операций, а для алгоритма B это число увеличится с 40 303. до 160 603 операций. Количество операций, выполняемых каждым алгоритмом, умножается на примерно четыре (хотя и не совсем точно).

С другой стороны, алгоритмы O (2ⁿ) или O (n!) имеют гораздо более высокие порядки роста, и это можно заметить даже для небольших значений n. Например, простой переход от n = 10 к n = 20 приведет к тому, что алгоритм O (2ⁿ) выполнит примерно на 1024 дополнительных операции. А для алгоритма O (n!) это означало бы в 670 миллиардов раз больше операций, чем раньше.

Формальные определения асимптотических обозначений.

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

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

Big O: верхние границы

До сих пор я использовал нотацию Big O в том виде, в котором она используется чаще всего: как точное описание эффективности алгоритма. Однако это технически неверно - как я покажу ниже, Big O предоставляет только способ представления верхних границ . Так что имейте в виду, что с этого момента я начну говорить о Big O в соответствии с его математическим определением, а не с тем, как он обычно используется на практике. (Если вас интересует более глубокое обсуждение этого очень распространенного заблуждения, вы можете проверить эту мою предыдущую статью.)

Неформально O (g (n)) можно понимать как набор математических функций, содержащий все функции, которые не « растут быстрее. ”, чем g (n). Например, O (n²) - это набор, содержащий n² + 3n, 3n, n, log (n) и бесконечное количество других функций, которые не растут быстрее, чем f (n) = n², когда n → ∞.

Вот как формально определяется Big O:

f (n) ∈ O (g (n)) тогда и только тогда, когда существуют некоторая положительная константа c и некоторое неотрицательное целое nₒ такие, что f (n) ≤ cg (n) для всех n ≥ nₒ.

Например, давайте проверим, 3n∈ O (n²). Взяв c = 1 и построив график функций f (n) = 3n и cg (n) = 1n², мы видим, что обе пересекаются в nₒ = 3:

Глядя на график, мы легко можем сказать, что 3n ≤ 1n² для всех n≥3. Но этого недостаточно, поскольку нам нужно на самом деле доказать это. Для этого мы можем использовать математическую индукцию. Это выглядит так:

1. Нам нужен базовый вариант nₒ, для которого мы знаем, что f (nₒ) ≤ cg (nₒ). Но у нас уже есть один, так как мы знаем, что можем использовать nₒ = 3.
2. Затем мы предполагаем, что f (n) ≤cg (n) для данного n≥nₒ. В нашем случае мы предполагаем, что 3n ≤ 1n² для данного n≥3.
3. Теперь нам нужно показать, что если f (n) ≤cg (n), то f (n + 1) ≤ cg (n + 1). В нашем случае нам нужно доказать, что если наше предположение (2) выше верно, то 3 (n + 1) ≤ (n + 1) ² также верно. Это также можно записать как 3n + 3 ≤ n² + 2n + 1. Но поскольку мы уже знаем из (2), что 3n ≤ n², мы можем вычесть 3n из левой части и n² из правой. неравенства, не влияя на его отношение. Это даст нам 3 ≤ 2n + 1. Поскольку мы знаем, что n≥3, это неравенство всегда будет выполняться при условии, что выполняется (2). Это завершает доказательство того, что 3n ≤ 1n² для всех n≥3, и, следовательно, 3n ∈ O (n²).

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

Большая Омега (Ω): нижняя граница

Big Omega определяется так же, как Big O, за исключением того, что представляет собой нижнюю границу, а не верхнюю границу. Таким образом, его формальное определение только меняет отношение между f (n) и cg (n). Другими словами, «≤» становится «≥»:

f (n) ∈ Ω (g (n)) тогда и только тогда, когда существуют некоторая положительная константа c и некоторое неотрицательное целое nₒ такие, что f (n) ≥cg (n) для всех n ≥ nₒ.

В качестве примера рассмотрим, что n³∈ Ω (2n³ + n). Чтобы доказать это утверждение, вы можете попробовать c = 1/3 и n = 1 и использовать индукционный подход, как описано выше. Вот графическое представление:

Большая тета (Θ): жесткие рамки

Bit Theta используется для обозначения жестких границ функций. Утверждение, что f (n) ∈ Θ (g (n)) означает, что f (n) имеет в точности то же самое порядок роста как g (n).

По сути, Большая Тета - это пересечение Большого О и Большой Омеги. Вот два простых определения Большой Теты, основанные на этом факте:

1) f (n) ∈ Θ (g (n)) тогда и только тогда, когда f (n) ∈ O (g (n)) и f (n) ∈ Ω (g (n)).

2) Θ(g(n))=O(g(n)) ⋂ Ω(g(n)).

Но Большую Тету также можно определить так же, как мы определили Big O и Big Omega выше, объединив оба определения вместе:

f (n) ∈ Θ (g (n)) тогда и только тогда, когда существуют некоторые положительные константы c ₁ и c₂ и некоторое неотрицательное целое nₒ такое, что c ₁ g (n) ≤ f (n) ≤ c₂ g (n) для всех п ≥ пₒ.

Как и в случае с Большой Омегой, мы также можем показать, что n³∈ Θ (2n³ + n). Для этого рассмотрим c₁ = 1/3, c₂ = 1/2 и nₒ = 1:

Маленькая Омега (ω) и Маленькая О (o): свободные границы

Правильно, асимптотические обозначения не всегда Большие. Существуют также две Маленькие нотации: Маленькая Омега (ω) и Маленькая О (о). Они используются не так часто, как Большие, но я люблю упоминать о них для полноты картины.

Эти два обозначения используются для представления не «жестких» нижних или верхних границ. Более конкретно, ω (g (n)) включает все функции, которые находятся в Ω (g (n)), но не в Θ (g (n)) . Формально ω (g (n)) = Ω (g (n)) - Θ (g (n)). Аналогичным образом o (g (n)) = O (g (n)) - Θ (g (n)).

Например, n²∈ o (n³), но n³∉ o (n³).

Вот формальные определения этих двух маленьких обозначений:

f (n) ∈ o (g (n)) тогда и только тогда, когда существует неотрицательное целое nₒ такое, что f (n) ≤cg (n) для всех n ≥ nₒ и для любой положительной константы c.

f (n) ∈ ω (g (n)) тогда и только тогда, когда существует неотрицательное целое nₒ такое, что f (n) ≥cg (n) для всех n ≥ nₒ и для любой положительной константы c.

Вы уловили разницу? В то время как для Big Omega и Big O достаточно одного значения c, для Little Omega и Little O требуется, чтобы свойство было действительным для любого значения c .

Использование пределов для сравнения двух функций

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

Для этого вам необходимо вычислить предел L = lim (f (n) / g (n)) при n → ∞. Если такой предел существует, его значение сразу же сообщает вам, какие асимптотические обозначения действительны при сравнении f (n) с g (n):

1. Если L = 0, то f (n) ∈ O (g (n)) и f (n) ∈ o (g (n)) .
2. Если L → ∞, то f (n) ∈ Ω (g (n)) и f (n) ∈ ω ( g (n)).
3. Для других постоянных значений L, тогда f (n) ∈ Θ (g (n)).

В качестве примера снова рассмотрим f (n) = n³ и g (n) = 2n³ + n. Для этих функций вы обнаружите, что L = 1/2, что означает, что n³∈ Θ (2n³ + n). ( Но обратите внимание, что по определению это также означает, что n³∈ Ω (2n³ + n) и n³∈ O (2n³ + n).)

Последние мысли

Чтобы использовать асимптотические обозначения, такие как Big O, вам действительно не нужно глубоко разбираться в математике, стоящей за ними. Тем не менее, может быть полезно знать, что они означают и как они определены, особенно когда связь между двумя функциями не так очевидна. Θ (log (n)) быстрее, чем Θ (√n)? O (2ⁿ) - это то же самое, что O (3ⁿ)? А как насчет Ω (log₂ (n)) и Ω (ln (n))? Теперь, когда вы знаете, как эти обозначения определяются математически, вы можете попытаться найти ответы на такие вопросы самостоятельно.

использованная литература

• Введение в разработку и анализ алгоритмов Анани Левитин.

Раскрытие информации: этот пост содержит одну или несколько ссылок из программы Amazon Services LLC Associates. Как аффилированное лицо я получаю комиссионные за покупки, сделанные по этим ссылкам, без каких-либо дополнительных затрат для клиента.

Статьи по Теме