Сложность и Big O

Оценка эффективности кода

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

Big O не измеряет скорость в секундах. Она описывает зависимость между размером входных данных (обозначается как $n$ ) и количеством операций, которые должен выполнить алгоритм. Это помогает нам сравнивать разные подходы к решению задачи и выбирать наиболее масштабируемый.

Big O описывает, как производительность алгоритма ухудшается с ростом объема входных данных. Чем медленнее растет время выполнения при увеличении $n$ , тем эффективнее алгоритм.

Мы оцениваем два ключевых аспекта: временную и пространственную сложность.

Временная сложность

other

Количество операций, которое выполняет алгоритм в зависимости от размера входных данных. Это наш основной фокус, так как именно вычислительные операции чаще всего «тормозят» интерфейс.

Пространственная сложность

other

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

Основные виды сложности

Давайте рассмотрим самые распространенные типы сложности на примерах из фронтенд-разработки.

$O(1)$ — Константная сложность Время выполнения не зависит от размера входных данных. Это идеальный сценарий.

// Получение элемента по id
// Неважно, сколько элементов на странице, поиск по id всегда быстрый.
function getElement(id) {
  return document.getElementById(id); 
}

// Добавление элемента в конец массива
const arr = [1, 2, 3];
arr.push(4); // O(1)

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

$O(n)$ — Линейная сложность Время выполнения растет прямо пропорционально количеству элементов $n$ . Если данных стало вдвое больше, операций тоже станет примерно вдвое больше.

// Поиск элемента в списке по классу
// Чтобы найти нужный элемент, браузеру нужно проверить каждый узел.
function findElementByClass(className) {
  const elements = document.querySelectorAll(`.${className}`); // n элементов
  // В худшем случае придется перебрать все n элементов
  for (let i = 0; i < elements.length; i++) {
    if (elements[i].textContent === 'Искомый текст') {
      return elements[i];
    }
  }
}

Одиночный цикл по коллекции — классический пример линейной сложности.

$O(n^2)$ — Квадратичная сложность Время выполнения растет пропорционально квадрату количества элементов. Этого следует избегать при работе с большими наборами данных.

// Рендеринг таблицы, где для каждой строки нужно пройти по всем столбцам
const rows = 100; // n
const cols = 100; // m
// Сложность будет O(n * m), если n=m, то O(n²)

for (let i = 0; i < rows; i++) {       // Внешний цикл (n раз)
  for (let j = 0; j < cols; j++) {   // Внутренний цикл (m раз)
    // Создаем и вставляем ячейку в DOM
  }
}

Вложенные циклы, где каждый цикл зависит от $n$ , приводят к квадратичной сложности. Если у вас есть массив из 1000 элементов, такой код выполнит 1 000 000 операций.

Сложность методов массивов

Многие стандартные методы JavaScript, которые кажутся простыми, на самом деле имеют разную сложность. Это важно учитывать при работе с большими массивами.

Метод	Временная сложность	Объяснение
`push()`	$O(1)$	Добавление в конец. Не требует сдвига других элементов.
`pop()`	$O(1)$	Удаление с конца. Также не требует сдвига.
`shift()`	$O(n)$	Удаление с начала. Все остальные элементы нужно сдвинуть влево.
`unshift()`	$O(n)$	Добавление в начало. Все существующие элементы нужно сдвинуть вправо.
`slice()`	$O(n)$	Создает новую копию части массива. Нужно скопировать $n$ элементов.
`splice()`	$O(n)$	Может удалять, заменять или добавлять элементы. Требует сдвига элементов.

Вывод: операции в начале массива (shift, unshift) гораздо «дороже», чем операции в конце (push, pop).

Сценарии и Event Loop

При анализе алгоритма мы обычно ориентируемся на худший сценарий (worst-case). Например, при поиске элемента в массиве мы предполагаем, что он находится в самом конце или отсутствует. Это дает нам верхнюю границу производительности.

Существуют также лучший (best-case) и средний (average-case) сценарии. Например, лучший случай для поиска — это когда искомый элемент находится в самом начале ( $O(1)$ ). Но полагаться на это рискованно.

Почему это так критично для фронтенда? JavaScript работает в одном потоке, используя модель Event Loop (цикл событий). Если вы запускаете долгую, ресурсоемкую операцию (например, цикл со сложностью $O(n^2)$ на большом $n$ ), вы блокируете основной поток. Пока эта задача не завершится, браузер не сможет обрабатывать другие события: клики, скролл, анимации. В результате пользователь видит «зависший» интерфейс.

Понимание Big O позволяет писать код, который не блокирует Event Loop и обеспечивает плавную работу приложения, даже когда данных становится много.

Quiz Questions 1/4

Что в первую очередь описывает нотация Big O?

Quiz Questions 2/4

Какова временная сложность (Big O) доступа к элементу массива по его индексу, например, myArray[5]?

Оценка сложности — это не точная наука, а способ мышления. Выбирая между двумя алгоритмами, отдавайте предпочтение тому, который лучше масштабируется.

LeetCode для Frontend разработчика