Какова временная сложность вызова includes внутри цикла?

Метод includes у массивов и строк выполняет линейный поиск: он поочерёдно сравнивает каждый элемент с искомым значением, пока не найдёт совпадение или не дойдёт до конца. Значит, в худшем случае его сложность равна O(n), где n — длина коллекции.

Что происходит внутри цикла

Если includes вызывается внутри цикла, который тоже проходит по массиву, сложности перемножаются:

• внешний цикл — O(n);
• каждый вызов includes — O(n);
• итог — O(n²).

На массиве из 10 000 элементов это уже около 100 миллионов операций сравнения, что заметно замедляет код.

Пример

const arr = [1, 2, 3, 4, 5];

// O(n^2): для каждого элемента снова перебираем массив
for (const x of arr) {
  if (arr.includes(x * 2)) {
    console.log(x);
  }
}

// O(n): заранее строим Set и проверяем за O(1)
const set = new Set(arr);
for (const x of arr) {
  if (set.has(x * 2)) {
    console.log(x);
  }
}

Как ускорить

1. Заменить массив на Set или Map — проверка наличия становится O(1).
2. Отсортировать данные и использовать бинарный поиск — O(log n) на запрос.
3. Иногда достаточно одного прохода с хеш-таблицей вместо вложенных циклов.

Итог: includes внутри цикла — типичная причина квадратичной сложности. Если коллекция большая и проверок много, стоит заранее построить Set или Map и получить линейное решение.