Выбор ответа Junior Сложность обновлено
Два независимых входа
Вопрос
Какая сложность у функции?
function common(a, b) {
const res = [];
for (const x of a) {
for (const y of b) {
if (x === y) res.push(x);
}
}
return res;
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n · m). Внешний цикл по a (n), внутренний по b (m): всего n·m итераций, O(n · m).
Варианты ответа
- O(n · m)правильный ответ
- O(n)
- O(n²)
- O(n + m)
Разбор
Внешний цикл по a (n), внутренний по b (m): всего n·m итераций, O(n · m). Когда входов два, сводить всё к одному n нельзя.
- O(n) и O(n + m): так было бы при последовательных, а не вложенных циклах.
- O(n²): верно только если n = m, в общем случае это неточная оценка.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.