Сегодня я хотел уделить несколько минут разговору о сложности, поскольку эта тема довольно часто поднимается в компьютерных науках, а также часто вызывает путаницу. Большое О, большое Ω, большое Θ, что это такое и что все это значит? Что ж, я рад, что вы спросили, а теперь приготовьтесь к науке!

Давайте начнем с математики для разминки, прежде чем закончить простым английским (читай: скучным) объяснением всего этого. Но еще до этого история!

Обозначение O(n) впервые появилось в книге Пола Бахмана Die Analytische Zahlentheorie (Аналитическая теория чисел), опубликованной в 1892 году, где оно упоминалось как «Ordnung von n» (Порядок n).

Обозначение Ω(n) было введено математиками Г.Х. Харди и Дж. Э. Литтлвуд в 1914 году для целей аналитической математики, а позже пересмотренное определение Ω (n) было представлено Дональдом Кнутом в 1976 году вместе с введением ретронима для O (n), назвав его Большой Омикрон. Мы сосредоточимся на этих определениях, поскольку Кнуту приписывают первое применение их для изучения сложности компьютерных алгоритмов.

Небольшое отступление: следует ли называть O(n) «О» или «Омикрон»? Что ж, на самом деле это не имеет значения, но в трудах Бахмана прямо указано, что это означает Ordnung, поэтому, по мнению этого скромного автора, «О» было бы семантически лучше, но это фокусируется на математическом фоне, в то время как рассмотрение чистой информатики использовало бы Кнут выбрал «Омикрон».

Так что же они все означают тогда? Что ж, давайте пробежимся по списку

Большое О

Если мы позволим f (n) и g (n) быть неотрицательными функциями со значениями, определенными на неотрицательных целых числах n, то f (n) есть O (g (n) тогда и только тогда, когда существует положительная вещественная константа c и натуральное число nₒ , такое что f(n) ⩽ c⋅g(n) для всех n › nₒ.

Большое Ω

Опять же, если мы допустим f(n) и g(n) неотрицательнозначными функциями, определенными на неотрицательных целых числах n, то f(n) есть Ω(g(n) тогда и только тогда, когда существуют положительная вещественная константа c и положительная целое число nₒ такое, что f(n) ≥ c⋅g(n) для всех n › nₒ.

Большой Θ

И, наконец, если мы допустим, что f (n) и g (n) будут неотрицательными функциями со значениями, определенными на неотрицательных целых числах n, то f (n) есть Θ (g (n)), если существуют две положительные действительные константы c₁ и c₂, и натуральное число nₒ такое, что c₁⋅g(n) ≤ f(n) ≤ c₂⋅g(n) для всех n › nₒ.

Вот полезный график (надеюсь)

Итак, давайте перейдем к более скучному объяснению этого.

  • f(n) равно O(g(n)) означает, что g(n) описывает верхнюю асимптотическую границу для f(n) или описывает наихудший сценарий для f(n) с точки зрения сложности.
  • f(n) is Ω(g(n)) означает, что g(n) описывает нижнюю асимптотическую границу для g(n) или описывает сценарий наилучшего случая для f(n) с точки зрения сложности.
  • f(n) is Θ(g(n)) означает, что g(n) описывает как верхнюю, так и нижнюю асимптотическую границу f(n), или что он описывает средний сценарий для f(n).

Та-да! Это было не так уж и плохо?

А теперь, как насчет маленького о? А маленький ω? Мы что-то забыли здесь? Да, забыли! На самом деле есть еще более веселые и забавные обозначения! Давайте просто кратко коснемся маленького o и маленького ω. Примечание. Их также называют малым o/малым ω.

Таким образом, f (n) является o (g (n)) тогда и только тогда, когда f (n) является O (g (n) и f (n) не является Θ (g (n)). Это означает, что g (n) — это верхняя асимптотическая граница f(n), но f(n) никогда не может быть равно g(n) Это как дополнительное ограничение на O(n), можно сказать.

Далее, f(n) является ω(g(n)) тогда и только тогда, когда существует положительная вещественная константа c и натуральное число nₒ, такие что 0 ≤ c⋅g(n) ≤ f(n) для всех n › нₒ. Лучше всего это можно описать как жесткую нижнюю границу.

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

Чтобы завершить этот пост, вот краткий список общих сложностей, отсортированных в порядке возрастания сложности. Кстати, это те, что на графике в начале поста. Какое совпадение!

O(1) — constant time
O(logn) — logarithmic time
O(n) — linear time
O(nlogn) — linearithmic time
O(n²) — quadratic time
O(cⁿ) — exponential time
O(n!) — factorial time

Для получения действительно хорошей справки о некоторых распространенных сложностях алгоритмов посетите этот сайт.