Что на самом деле означает "Big O"

В большинстве случаев нотация Big O используется немного неправильно.

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

После изучения кода кандидат A сообщает вам, что этот алгоритм O (n). С другой стороны, кандидат B сообщает вам, что это O (n²). Основываясь на их ответах, какой из этих двух кандидатов, по вашему мнению, лучше подготовлен к работе?

Наверное, кандидат А, верно?

Но что, если я скажу вам, что оба ответа верны?

Обозначение Big O представляет собой верхнюю границу

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

Неформально O (g (n)) можно определить как набор математических функций, содержащий все функции, которые не « растут быстрее ”, чем g (n). Таким образом, все функции ниже находятся в наборе O (n²):

• f(n) = n²+3n + 2
• f (n) = n журнал (n)
• f(n) = 3n+1
• f(n) =n
• f (n) = log (n)
• f(n) =1

С другой стороны, f (n) = n³ не входит в O (n²), потому что f (n) = n³ растет быстрее, чем g (n) = n².

Снова рассмотрим пример из приведенного выше кода Java. В худшем случае этот алгоритм выполняет n сравнений. Кандидат A, очевидно, был прав, говоря, что это O (n). Но кандидат B был также прав, когда сказал, что алгоритм O (n²), потому что, действительно, f (n) = n содержится в O (n²). Тем не менее, он, вероятно, не получит работу.

Узкие рамки и большая тета (Θ)

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

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

На самом деле существует обозначение, похожее на Big O, которое точно отражает то, что рекрутеры ожидают от кандидатов. Он называется нотацией Big Theta (Θ) и используется для обозначения жестких границ функций. Утверждение, что f (n) равно Θ (g (n)), означает, что f (n) имеет тот же порядок роста, что и g (n). Несколько примеров:

• n² ∈ Θ(n²)
• 2n² ∈ Θ(n²)
• n² + 3n + 2 ∈ Θ(n²)
• n ∉ Θ(n²)
• n³ ∉ Θ(n²).

Рассмотрим снова пример выше, но теперь представьте, что вы переформулируете свой вопрос и спрашиваете двух кандидатов об эффективности алгоритма с точки зрения нотации Big Theta. Если кандидат А говорит, что алгоритм работает в Θ (n), он снова будет прав. Но если кандидат B скажет, что это выполняется в Θ (n²), теперь он будет абсолютно неправ, а вы будете правы, заключив, что он, вероятно, не подходит для этой работы.

Когда люди говорят об эффективности алгоритма, большую часть времени они заинтересованы в получении жестких границ этой эффективности. Но вместо того, чтобы использовать для этого Big Theta, они обычно используют Big O. Я предполагаю, что в какой-то момент кто-то решил, что фраза «ой из n» звучит намного лучше, чем «theta of n», и в итоге это стало норма.

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

Большая Омега (Ω)

Помимо Big O и Big Theta, в алгоритмическом анализе часто используется третья асимптотическая нотация: Big Omega (Ω). Это можно понимать как обратное к Big O, поскольку оно представляет собой нижнюю границу для набора математических функций: Ω (g (n)) - это набор всех функций, которые не выполняются. имеют меньший порядок роста , чем g (n). Например, n³∈ Ω (n²) и n²∈ Ω (n²), но n∉ Ω (n²).

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

Понимание Большой Омеги на самом деле упрощает определение Большой Теты: Θ (g (n)) - это пересечение O (g (n)) и Ω ( g (n)). Функция f (n) находится в Θ (g (n)) тогда и только тогда, когда они обе находятся в Ω (g (n)) и O (g (n)).

Математические определения

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

Резюме и заключительные мысли

В большинстве случаев люди используют Big O, чтобы описать жесткие рамки. Однако Big O - это, по определению, формализм для описания верхних границ, а не жестких границ. Если данный алгоритм равен O (n), он также может быть назван O (n²), O (n³), и бесконечным другие классы эффективности. Аналогичное обозначение, Big Theta (Θ), гораздо лучше описывает эффективность данного алгоритма, поскольку оно обеспечивает способ точного описания жестких границ. Тем не менее, многие люди никогда не слышали о Большой Тете, поскольку она редко используется на практике.

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

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

• Большая тета-нотация в Ханской академии.
• Введение в разработку и анализ алгоритмов Анани Левитин.

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

Еще от того же автора