Выбор ответа Junior Сложность спрашивают часто обновлено
Скрытый цикл в includes
Вопрос
Функция убирает дубликаты. Какая у неё сложность по времени и как сделать лучше?
function unique(arr) {
const res = [];
for (const x of arr) {
if (!res.includes(x)) res.push(x);
}
return res;
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n²); с Set будет O(n). Array.prototype.includes линейный: на каждом из n шагов он просматривает до n элементов, итого O(n²).
Варианты ответа
- O(n²); с
Setбудет O(n)правильный ответ - O(n),
includesработает за O(1) - O(n log n); быстрее нельзя
- O(n²); быстрее только через сортировку за O(n log n)
Разбор
Array.prototype.includes линейный: на каждом из n шагов он просматривает до n элементов, итого O(n²). Set.has в среднем O(1), поэтому [...new Set(arr)] даёт O(n).
includesне O(1): это проход по массиву.- Сортировка даст O(n log n), но это не лучший вариант: Set быстрее и сохраняет порядок первого появления.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.