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

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

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

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

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

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

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

Алгоритм 1:

def sockCounter (numberOfPairs):
IndividualSocks = 0
для x в диапазоне (numberOfPairs):
индивидуальные носки = индивидуальные носки + 2
вернуть индивидуальные носки

Алгоритм 2:

def sockCounter (numberOfPairs):
возврат 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 был бы выражен как один:

О (1)

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

На)

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

Линейный код

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

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

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

def searchForValue (targetValue, arraySearched):
foundTarget = Ложь
для x в arraySearched:
для y в x:
если (y == targetValue):
foundTarget = True
вернуть foundTarget

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

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

O (n²)

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

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

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

журнал 2 (8) = 3

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

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

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

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

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

O (журнал (п))

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

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

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

10 самых распространенных ошибок программирования и кодирования

Ошибки кодирования могут привести к множеству проблем. Эти советы помогут вам избежать ошибок программирования и сохранить смысл кода.

Об авторе