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

Нотация Big O — это способ простого представления того, как время выполнения функции зависит от количества данных, передаваемых в эту функцию, или от временной сложности этой функции. Это представление будет выглядеть как заглавная буква «O» (не представляющая ничего важного), за которой следует скобка, содержащая строчную букву «n» (представляющую количество данных, передаваемых в функцию) и любой модифицирующий символ, соответствующий сложности функции.

(Примечание: Не беспокойтесь о том, что означает «О». Какой-то очень старый человек давным-давно решил, что это означает «порядок», но это не имеет никакого отношения к уравнениям, которые вы найдете внутри скобок. «О» — это просто условность).

Если вы займетесь изучением нотации Big O, то очень быстро наткнетесь на графики, которые выглядят примерно так:

Этот график показывает, как каждая нотация связана с количеством операций, которые необходимы при увеличении числа элементов. Время выполнения функции будет увеличиваться с ростом числа операций, однако связь между временем и данными и связь между операциями и данными не всегда совпадают. Тем не менее, можно с уверенностью сказать, что больше операций равняется большему времени. С учетом сказанного, давайте разберемся в перечисленных выше обозначениях, начиная с самого простого и продвигаясь дальше, остановившись (пока) на O(log n)

O(1)

Функция, имеющая временную сложность O(1), будет выполняться одинаковое количество времени и использовать одинаковое количество операций независимо от того, сколько данных передается в функцию. Обычно это означает функцию, которая либо ничего не делает с данными (что кажется мне не очень практичным), либо делает что-то с очень специфической частью данных, как функция .push() в JavaScript. Независимо от того, сколько элементов находится в массиве, к которому вы хотите выполнить push, добавление элемента в массив всегда будет занимать одинаковое количество времени.

O(n)

Функция с временной сложностью O(n) займет время, линейно пропорциональное количеству переданных данных.

Забудьте на секунду о коде: сколько времени вам потребуется, чтобы сосчитать 1 секунду? Надеюсь, около 1 секунды. Сколько времени вам нужно, чтобы досчитать до 2 секунд? Как насчет 3? 4? Соотношение между временем, которое вам потребуется, чтобы сосчитать любое число (n) секунд, и количеством секунд, которые пройдут, пока вы считаете, всегда будет одинаковым, независимо от того, считаете ли вы 4 секунды или сто миллиардов секунд.

Вернемся к коду: Любая функция, которая поддерживает соотношение между количеством переданных данных и количеством времени до завершения работы, будет иметь временную сложность O(n). Пример:

function printArr (arr) {
   for (let i = 0; i < arr.length; i++) { // for every element...
      console.log(arr[i]) // console log it.
   }
}

Количество времени, необходимое для выполнения console.log(), останется неизменным независимо от того, сколько элементов находится в массиве. Единственное, что меняется, — это количество элементов, необходимых для записи в журнал. Соотношение между данными и временем обработки всегда будет одинаковым, независимо от количества данных.

O(n²)

В случае функции с временной сложностью
O(n²), количество операций, выполняемых в функции, прямо пропорционально количеству элементов в квадрате.

Забывание кода: Представьте, что вам нужно посчитать, чтобы полить 5 растений, но для каждого растения, которое вы поливаете, вам нужно пересчитать все растения. Чтобы полить все растения, вам придется пересчитать каждое из 5 растений 5 раз, итого 25 пересчитанных растений. И 5² это 25! Независимо от количества растений, которые вам нужно полить, если вам нужно пересчитывать все растения каждый раз, когда вы поливаете одно из них, количество пересчитанных растений всегда будет равно n².

Вернемся к коду: В коде это проявится в виде циклов внутри циклов. Пример:

const arr = [1, 2, 3]

const printArrArrs = (arr) => {
    // for every element: "i loop"
   for (let i = 0; i < arr.length; i++) { 
      // for every element: "j loop"
      for (let j = 0; j < arr.length; j++) { 
      // console log that element
      console.log(arr[j])
      }
   }
}

printArrArrs(arr)

В этом коде наш «i-цикл» будет выполняться один раз для каждого элемента в arr. Для каждого цикла «i loop» наш «j loop» будет повторять цикл по arr, и в консоли будет записываться каждый элемент. В консоли должно быть 9 чисел, потому что 3² 9. При любой длине массива arr количество элементов, записываемых в консоль, всегда будет прямо пропорционально квадрату длины массива.

2 Быстрые примечания!

Примечание 1: При определении правильной нотации для функции важен только самый сложный слой функции. В приведенном выше примере есть три слоя кода: console.log() внизу, «j-цикл» в середине и «i-цикл» вверху. Временная сложность console.log() равна O(1), поскольку каждый раз будет выполняться одно и то же количество операций. Цикл «j loop» имеет временную сложность O(n), поскольку он будет выполнять содержащийся в нем код один раз для каждого элемента массива. Цикл «i» — единственная часть функции, которая имеет временную сложность O(n²), поэтому временная сложность всей функции равна O(n²).

Примечание 2.a: То, о чем мы говорили в связи с O(n²) может масштабироваться для любого количества вложенных циклов. Если в функции есть три вложенных цикла, то временная сложность этой функции равна O(n⁴). Если у вас есть 4 цикла, вложенных друг в друга, то ее временная сложность равна O(n⁴).

Примечание 2.b: В результате замечания 2.a, при определении правильной нотации для функции с несколькими циклами в ней, имейте в виду, что 2 цикла не обязательно означают, что временная сложность функции равна O(n²). Это справедливо только для вложенных циклов.

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

O(log n)

Что подождать? Что такое «log»…?

Что такое «log»?

«log» — это сокращение от «logarithm». Логарифм — это число (y), к которому нужно возвести другое число (называемое основанием), чтобы получить данное число. Нотация для логарифма будет выглядеть так: «log_{основание}x = ?» В информатике наше основание всегда будет равно 2, поэтому вместо того, чтобы писать основание, мы просто… не пишем. Таким образом, обозначение записывается как O(log n), а пробел — это исключаемое основание.

Вернемся к O(log n)

Учитывая то, что мы узнали о логарифмах, функция с временной сложностью O(log n) — это функция, в которой количество выполняемых операций равно log₂n, где «n» представляет собой количество циклов функции. Лучший способ думать о связи между операциями и данными здесь заключается в том, что количество операций увеличивается линейно, поскольку данные увеличиваются экспоненциально.

Забывание кода: Представьте, что вы хотите найти имя своего друга «Джон Стоктон» в отсортированном по алфавиту школьном ежегоднике, в котором 100 человек. На каждой странице есть один человек. Вы могли бы искать на каждой странице, но это было бы медленно. Вместо этого вы открываете книгу на половине страницы, проверяете, совпадает ли там имя вашего друга, и если нет, то выбираете сторону, которая ближе к его имени по алфавиту, и снова разделяете. Продолжайте делать это до тех пор, пока не найдете его имя. Этот метод будет иметь временную сложность O(log n), потому что независимо от того, сколько имен было 10, 100 или 1000, максимальное количество операций, которое может быть выполнено, будет равно log₂10 или 100 или 1000 (n)

Вернемся к коду: На этот раз я не стал писать свой собственный пример. Самый простой пример кода, который я смог найти для O(log n), был этот. Честно говоря, если вы хотите получить лучшее объяснение O(log n), я рекомендую вам посмотреть это видео целиком.

const n = 8

function logn(n) {
  while (n > 1) { // while n is greater than 1
    n = Math.floor(n/2) // divide n by 2 (and remove remainder)
  }
}

logn(n)

В приведенном выше коде в функцию logn() передается 8. Используя псевдокод, давайте рассмотрим, что происходит с n. Сначала n передается в виде 8. 8 больше 1, поэтому оно делится пополам (8/2=4). Затем его снова передают как 4, что больше 1, поэтому его снова делят пополам. Затем оно снова передается как 2, уменьшается вдвое, а затем снова передается как 1, и в этот момент n уже не больше 1. В этом примере кода потребовалось 3 итерации, чтобы добраться до 1, что означает, что log n равен 3. Хотя это отлично подходит для вычисления log числа, как это поможет нам определить/написать алгоритмы с временной сложностью O(log n)? В общем случае, как и в данном случае, если данные, переданные в функцию, делятся на 2 и используются снова, то функция, вероятно, имеет временную сложность O(log n). Но более конкретно, пройдя через этот процесс для одного числа, мы можем сказать, что количество выполняемых операций всегда будет масштабироваться пропорционально log₂ любого числа, которое мы передаем в качестве n.

Заключение

Из всего, что я рассмотрел, следует, что нотация Big O не так уж и сложна. До этого я в основном не знал о логарифмах, поэтому на O(log n) ушло немного больше времени, но по сути это просто обратное O(n²), в чем я чувствую себя достаточно хорошо разбирающимся. В любом случае, я получил массу удовольствия, исследуя все это, и надеюсь, что то, что я написал, будет полезно всем, кто в этом нуждается.