Big O notation

Каждый алгоритм можно оценить по времени и по памяти. При этом, не совсем понятно, как объективно составить эту оценку. Для решения этого вопроса существует O notation.

Это серьезный математически термин, который позволяет установить порядки сравнения поведения функций.

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

Рассмотрим примеры некоторых оценок по сложности:

— Константная сложность O(1)
Константная сложность по времени гласит «Вне зависимости от объема данных, скорость выполнения неизменна»

В коде это, например, обращение к объекту по ключу. Вне зависимости от размера объекта, значение по ключу доступно с константной сложностью.

— Линейная сложность O(n)
Алгоритм линейной сложности по времени — такой алгоритм, время выполнения которого прямо пропорционально объёму данных. Например, это метод reduce

[1, 2, 3, 4].reduce((acc, cur) => acc + cur, 0)

— Квадратная скорость O(n^2)
То есть время выполнения есть квадрат объёма данных. Это может быть тот же reduce, но примененный уже не для массива, а для матрицы, то есть это работа цикла внутри другого цикла.

matrix.reduce((acc, cur) => 
 acc + cur.reduce((acc, cur) => acc + cur, 0), 0)

Этот код найдет сумму всех элементов матрицы.

Если же говорить об оценке по времени, то оценки могут быть такими же по величине, что и по сложности, то есть O(1), O(n)…

Рассмотрим пример, где сложность алгоритма по памяти — O(n):

const countElements = (arr) => {
 const counts = {}
 
 for (let i = 0; i < arr.length; i++) {
  const key = arr[i] 
  if (counts[key]) {
   counts[key] += 1
  } else {
   counts[key] = 1
  }
 }

 return counts
}

В этом коде размер объекта counts может расти прямо пропорционально длине массива, потому что каждого из элементов массива может быть представлен в единственном экземпляре. Размер входных параметров при оценке по памяти не учитывается.

Также стоит помнить, что при оценке алгоритма мы отбрасываем константы. То есть алгоритм сложностью O(3n) на самом деле равняется O(n), и так далее.

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

Спасибо за прочтение, это важно ❤️

#theory #useful