Алгоритмы trainee
Что такое жадный алгоритм?
Ответ
На каждом шаге делаешь локально оптимальный выбор, надеясь, что в итоге получится глобально оптимальное решение. Работает не всегда (нужно доказывать)! Пример где работает: размен сдачи стандартными монетами.
Разбор: Жадный алгоритм на каждом шаге делает локально оптимальный выбор в надежде получить глобальный оптимум, но это срабатывает не всегда (нужно доказывать). Первый дистрактор описывает полный перебор/backtracking с гарантией оптимума, второй — динамическое программирование с мемоизацией подзадач, третий — рандомизированный подход; все три путают жадность со смежными парадигмами, у которых иной принцип принятия решения.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.