Выбор ответа Middle Динамическое программирование обновлено
Сложность мемоизации
Вопрос
Какая сложность у функции с мемоизацией для сетки m × n?
function paths(m, n, r = 0, c = 0, memo = new Map()) {
if (r === m - 1 || c === n - 1) return 1;
const key = r + ',' + c;
if (memo.has(key)) return memo.get(key);
const res = paths(m, n, r + 1, c, memo) + paths(m, n, r, c + 1, memo);
memo.set(key, res);
return res;
}
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(m · n) времени и памяти на кеш. Каждое состояние (r, c) вычисляется один раз, на остальные вызовы отвечает кеш, работа на состояние O(1).
Варианты ответа
- O(2^(m+n)), как без мемоизации
- O(m · n) времени и памяти на кешправильный ответ
- O(m + n): длина одного пути
- O((m + n)!) по числу путей
Разбор
Каждое состояние (r, c) вычисляется один раз, на остальные вызовы отвечает кеш, работа на состояние O(1). Итого O(m · n). Память: кеш O(m · n) плюс стек O(m + n).
- O(2^(m+n)) без мемоизации.
- O(m + n) это только глубина рекурсии.
- Факториал не возникает.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Предыдущий вопрос
Наибольшая возрастающая подпоследовательность
Следующий вопрос
Сделать массив великим