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

Что такое нотация 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².

зеркало экрана Android на ПК по беспроводной сети

Кредит изображения: Ник Фледдерус / Существительное Проект

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

O(n²)

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

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

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

log 2 (8) = 3

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

Кредит изображения: Ник Фледдерус / Существительное Проект

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

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

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

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

O(log(n))

Важность нотации большого O

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

для чего используется виртуальная машина

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

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

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

Читать далее Похожие темы
  • Программирование
  • Программирование
Об авторе Дженнифер Ситон(Опубликовано 21 статья)

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

Ещё от Jennifer Seaton

Подписывайтесь на нашу новостную рассылку

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

Нажмите здесь, чтобы подписаться