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

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

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

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

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

Как вы рассчитываете нотацию большого O

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

Алгоритм 1:

  def sockCounter (numberOfPairs):  
IndividualSocks = 0
для x в диапазоне (numberOfPairs):
IndividualSocks = IndividualSocks + 2
return IndividualSocks

Алгоритм 2:

  def sockCounter (numberOfPairs): 
return numberOfPairs * 2

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

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

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

  1. Он присваивает нулевое значение переменной IndividualSocks.
  2. Он присваивает значение единицы переменной i.
  3. Он сравнивает значение i с numberOfPairs.
  4. Он добавляет два к отдельным носкам.
  5. Он присваивает себе повышенное значение IndividualSocks.
  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
для x в arraySearched:
для y в x:
if (y == targetValue):
foundTarget = True
return foundTarget

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

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

O(n²) 

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

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

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

  log 2 (8) = 3  

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

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

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

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

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

  O (log (n  ))  

Важность нотации Big-O

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

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

.

Оцените статью
oilgasindustry.ru
Добавить комментарий