Простое руководство по сложности

Цель

Эта статья действует как введение в сложности для инженеров. Тем не менее, это будет наиболее полезно для разработчиков, которые уже имеют приблизительное представление об этой области и хотят освежить в памяти некоторые основные методы и терминологию.

Аргумент

«Большой O» — это измерение того, как время связано с входными переменными. Чтобы объяснить, давайте возьмем пример. У нас есть алгоритм, который проходит через массив, печатая каждый элемент. Если n размер массива, то мы сделаем n шагов. Поэтому наша сложность равна O(n).

Возьмем другой алгоритм, который генерирует все пары элементов в двух массивах. Первый массив имеет длину m, а второй массив имеет длину n. Для каждого элемента в первом массиве нам нужно было бы просмотреть каждый элемент в массиве два, что означает, что мы умножим m на n шагов. Сложность O(m * n)

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

Есть некоторые правила, чтобы согласиться с этими понятиями.

  • Удалить константы. Алгоритм O(2n) аналогичен алгоритму O(n).
  • Отбрасывать недоминирующие термины. Доминирующий термин — это термин, который больше всего влияет на сложность. Сложность O(n^2 + n) становится O(n^2).

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

Последнее правило такое.

  • Все термины журнала с постоянной базой эквивалентны. Термин log(n) с основанием 2 эквивалентен log(n) с любым другим постоянным основанием.

График в начале этой статьи — отличное руководство, помогающее решить, какой термин является доминирующим в вашей сложности, а также порядок сложности. Однако сложно получить их все в одном четком визуальном представлении. Наиболее распространенные из них в порядке скорости:

  1. Постоянная O(c)
  2. Логарифмический O(log(n))
  3. Линейный O(n)
  4. Линейно-арифмический O(n log(n))
  5. Полином O(n^c)
  6. Журнал полиномиального умноженияO(n^c log(n)) *
  7. Экспоненциальный O(c^n)
  8. ФакториалO(n!)

* Это зависит от значения c, у нас есть O(n^b log(n)) ‹ O(n^c) ‹ O(n^c log(n)) , пока b < c.

На самом деле существует три типа асимптотических обозначений.

  1. Обозначение Big-θ (Big-Theta)
  2. Обозначение Big-O
  3. Обозначение Big-Ω (Big-Omega)

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

Big-θ (Big-Theta) — это идея о том, что по мере увеличения n у нас появляется свойство

k_1 * f(n) < Run Time < k_2 * f(n)

Где k_1 и k_2 — некоторые константы. Большая тета требует определенной степени точности, в следующих примерах мы будем компенсировать это.

Big O заботится только об асимптотической верхней границе (фиолетовая линия на диаграмме). То есть у нас есть свойство

Run Time < k_2 * f(n)

Используя это определение, мы получаем, что алгоритм, который является O(n), также является O(n^2), поскольку он по-прежнему обеспечивает верхнюю границу нашего времени выполнения. Мы знаем, что наше время выполнения всегда будет меньше, чем наша функция.

Big-Ω (Big-Omega) дает только нижнюю границу (зеленая линия на диаграмме). Это эквивалентно

k_1 * f(n) < Run Time

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

Мы можем использовать эти понятия для определения асимптотических отношений между функциями. Например, мы знаем, что по мере увеличения n n^k будет меньше, чем c^n, где k и c являются константами. Поэтому мы можем сказать, что n^k равно O(c^n).

Вывод

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