Frontend-разработка

Forwarded from Senior Frontend - javascript, html, css

Как анализировать алгоритмы?

Вычислительная сложность алгоритма описывает, как выполняемый алгоритмом объём работы зависит от размера входных данных.
Обычно у алгоритмов бывает две сложности:

- временная сложность — как количество операций, которые выполняются при работе алгоритма, связано с объёмом входных данных;
- сложность по памяти — как количество памяти, которое нужно алгоритму, связано с размером входных данных.
В обоих случаях оцениваем, как связаны используемые алгоритмом ресурсы (время или память) с количеством входных данных. Может показаться, что алгоритм медленнее работает и потребляет больше памяти, когда размер входных данных большой. Это не всегда так. К примеру, скорее всего время работы функции const doNothing = (...asManyDataAsYouLike) => { } не будет зависеть от количества переданных ей аргументов. Оценка сложности этой функции — O(1). Попробуем разобраться, что это значит.

Способы оценки сложности (обозначения)
Есть несколько способов оценки сложности алгоритмов. Их основная идея – получить ограничение для функции, которая связывает размер входных данных и количество операций или размер памяти. Не стоит определять эту функцию точно, нам нужна именно оценка.

O (О-большое)
O, читается как «О», «О-большое» или «биг (big) О», описывает оценку сложности сверху. То есть максимальное количество операций, которое алгоритм может выполнить в худшем случае. В скобках после О указывают функцию, которая ограничивает сложность. Например, O(n) означает, что сложность алгоритма растёт линейно. Это означает, что время выполнения алгоритма увеличивается прямо пропорционально размеру входных данных (к примеру, есть список из 10 элементов, алгоритм займёт определённое время. Но если будет 20 элементов, то алгоритм займёт в два раза больше времени). При этом как именно линейно не важно. Давайте рассмотрим несколько примеров.

Вычислительная сложность этого алгоритма — O(n). Мы обрабатываем каждый элемент один раз. Если в нашем массиве n элементов, мы выполним тело функции reduce n раз.
const sum = (someArray) => someArray.reduce((sum, value) => sum + value, 0)

Вычислительная сложность этого алгоритма тоже будет O(n). Мы обрабатываем каждый элемент два раза. Если в нашем массиве n элементов, то выполним тело функции reduce 2 × n раз. n раз для суммирования и n раз для произведения. Это описывает формула O(k × n) = O(n). В нашем случае коэффициент не имеет значения, так как он не зависит от размера входных данных.

 const sumAndProd = (someArray) => {
   const sum = (someArray) => someArray.reduce((sum, value) => sum + value, 0)
   const prod = (someArray) => someArray.reduce((prod, value) => prod * value, 1)
   return sum * prod
 }

👉 @seniorFront

1 view10:30