Сложность пересечения через includes

Question

Какова сложность функции при длинах массивов n и m, и как её улучшить? const intersect = (a, b) = a.filter((x) = b.includes(x));

Техпрогон · Accepted Answer

Правильный ответ: O(n·m); если положить b в Set и проверять has, будет O(n + m). includes у массива перебирает элементы линейно, и он вызывается для каждого из n элементов a: итого O(n·m). O(n·m); если положить b в Set и проверять has, будет O(n + m). includes у массива перебирает элементы линейно, и он вызывается для каждого из n элементов a: итого O(n·m). Set.has в среднем работает за O(1), поэтому const s = new Set(b); a.filter((x) = s.has(x)) даёт O(n + m) по времени и O(m) по памяти. Бинарного поиска includes не делает: массив не обязан быть отсортирован.

Сложность пересечения через includes

Вопрос

Попробуйте сами

Коротко

Варианты ответа

Разбор

Ещё по теме «Разминка: короткие функции»