Выбор ответа Senior Жадные обновлено
Как обосновать жадность
Вопрос
Интервьюер спрашивает: «Почему твоя жадность верна?» Какой ответ правильный по сути?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Обмен: любой оптимум можно перестроить под жадный выбор. Стандартное обоснование: обменный аргумент или «жадный выбор остаётся впереди».
Варианты ответа
- «Она прошла все примеры из условия и мои крайние случаи»
- «Жадные алгоритмы всегда оптимальны, если выбор локально лучший»
- Обмен: любой оптимум можно перестроить под жадный выборправильный ответ
- «Потому что сложность O(n), а более быстрое решение невозможно»
Разбор
Стандартное обоснование: обменный аргумент или «жадный выбор остаётся впереди». Показываем, что жадный шаг совместим с каким-то оптимумом, а оставшаяся задача того же вида.
- Примеры не доказательство: пример с монетами 1, 3, 4 ломает жадность.
- Жадность часто неверна.
- Скорость не говорит о корректности.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.