Что такое нотация Big-O?

Дядя Влад

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

Что такое нотация Big-O?

Нотация Big-O позволяет рассчитать, сколько времени потребуется для запуска вашего кода. Вы можете физически рассчитать время, необходимое для запуска вашего кода, но с этим методом трудно уловить небольшие различия во времени. Например, между запуском от 20 до 50 строк кода очень мало времени. Однако в большой программе эти недостатки могут складываться.

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

Как вы вычисляете нотацию Big-O

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

Алгоритм 1:

 def sockCounter(numberOfPairs):
 individualSocks = 0
 for x in range(numberOfPairs):
 individualSocks = individualSocks + 2
 return individualSocks

Алгоритм 2:

 def sockCounter(numberOfPairs):
 return numberOfPairs * 2

Это глупый пример, и вы легко сможете определить, какой алгоритм более эффективен. Но для практики давайте пробежимся по каждому.

СВЯЗАННЫЕ: Что такое функция в программировании?

Алгоритм 1 состоит из множества шагов:

  1. Он присваивает нулевое значение переменной IndividualSocks.
  2. Он присваивает значение единицы переменной i.
  3. Он сравнивает значение i с numberOfPairs.
  4. Он добавляет два к индивидуальным носкам.
  5. Он присваивает себе повышенную ценность индивидуальных носков.
  6. Он увеличивает i на единицу.
  7. Затем он повторяет шаги с 3 по 6 столько же раз, что и (indiviualSocks – 1).

Количество шагов, которые мы должны выполнить для первого алгоритма, можно выразить как:

 4n + 2

Мы должны выполнить четыре шага n раз. В этом случае n будет равно значению numberOfPairs. Также есть 2 шага, которые выполняются один раз.

Для сравнения, у алгоритма 2 всего один шаг. Значение numberOfPairs умножается на два. Мы бы выразили это как:

 1

Если это еще не было очевидно, теперь мы можем легко увидеть, что алгоритм 2 намного эффективнее.

Анализ Big-O

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

В приведенных выше примерах алгоритм 2 был бы выражен как один:

 O(1)

Но алгоритм 1 можно упростить как:

 O(n)

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

Линейный код

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

Квадратичный код

Не все отношения так просты, как линейный пример. Представьте, что у вас есть 2D-массив, и вы хотите найти в нем значение. Вы можете создать такой алгоритм:

 def searchForValue(targetValue, arraySearched):
 foundTarget = False
 for x in arraySearched:
 for y in x:
 if(y == targetValue):
 foundTarget = True
 return foundTarget

В этом примере количество шагов зависит от количества массивов в arraySearched и количества значений в каждом массиве. Таким образом, упрощенное количество шагов будет n * n или n².

Это отношение является квадратичным, а это означает, что количество шагов в нашем алгоритме растет экспоненциально с увеличением n. В нотации Big-O вы могли бы записать это как:

 O(n²)

СВЯЗАННЫЕ: полезные инструменты для проверки, очистки и оптимизации файлов CSS

Логарифмический код

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

 log 2 (8) = 3

Журнал равен трем, потому что, если бы наша база была 2, нам потребовалось бы значение экспоненты 3, чтобы получить число 8.

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

На первый взгляд это кажется нелогичным. Как шаги алгоритма могут расти медленнее, чем n? Хороший пример – бинарный поиск. Рассмотрим алгоритм поиска числа в массиве уникальных значений.

  • Мы начнем с поиска в массиве в порядке от наименьшего к наибольшему.
  • Далее мы проверим значение в середине массива.
  • Если ваше число больше, мы исключим более низкие числа из нашего поиска, а если число было меньше, мы исключим более высокие числа.
  • Теперь посмотрим на среднее число оставшихся чисел.
  • Опять же, мы исключим половину чисел в зависимости от того, является ли наше целевое значение выше или ниже среднего значения.
  • Мы продолжим этот процесс, пока не найдем нашу цель или не определим, что ее нет в списке.

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

 O(log(n))

Важность обозначения Big-O

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

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