Жадный подход
Выбирайте лучший шаг и не оглядывайтесь назад
«Жадный подход» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что означает жадный алгоритм
Жадный алгоритм строит ответ шаг за шагом: каждый раз он выбирает вариант, который кажется лучшим прямо сейчас, и позже уже не отменяет свой выбор. ⚡
Выбор лучшего шага
В каждый момент задавайте себе один вопрос: какой единственный вариант приносит наибольшую пользу локально? Выбирайте его и переходите к следующему решению.
Не оглядывайтесь назад
Жадный алгоритм принимает решение и никогда не отменяет его. В отличие от поиска с возвратом, он не исследует другие пути — именно поэтому он настолько быстр.
Почему жадный алгоритм быстр
Поскольку он принимает одно решение на каждом шаге, жадный алгоритм обычно работает за O(n) или O(n log n) после сортировки. В соревнованиях это его главное преимущество.
Привычка сортировать
Большинство жадных решений начинается с сортировки элементов. Порядок показывает, какой элемент очевидно лучше выбрать на каждом этапе.
items.sort(key=lambda x: x.cost)Свойство жадного выбора
Жадный алгоритм работает только тогда, когда локально лучший выбор входит хотя бы в один глобально лучший ответ. Это и есть свойство жадного выбора.
Он не всегда прав
Выбор лучшего шага прямо сейчас всё равно может привести к ошибке в целом. Размен монет с необычными номиналами — классический пример, когда жадный алгоритм даёт неправильную сумму.
Докажите или проверьте
Прежде чем доверять жадному алгоритму, обоснуйте его доказательством обмена или проверьте на небольших входных данных, сравнив с полным перебором.
Доказательство обменом
В доказательстве обменом жадный выбор заменяет часть оптимального ответа, после чего показывается, что результат не стал хуже. Если это верно, жадный алгоритм безопасен.
Короткий цикл жадного алгоритма
Вот структура почти любого жадного алгоритма: отсортировать, а затем один раз пройти список, выбирая всё, что подходит под ваше правило.
items.sort()
for x in items:
if fits(x):
take(x)Когда выбирать жадный алгоритм
Попробуйте жадный алгоритм, когда понятный порядок ранжирует варианты и одно правило постоянно оказывается выигрышным. Если варианты сложно взаимодействуют друг с другом, склоняйтесь к DP.
Быстрая проверка
Вы решаете, можно ли доверять жадному подходу.
Итоги
Жадный алгоритм выбирает лучший локальный шаг и не оглядывается назад, обычно предварительно отсортировав данные. Он быстр, но корректен только тогда, когда жадный выбор можно доказать. 🚀
Часто задаваемые вопросы
Урок «Жадный подход» бесплатный?
Да — полный текст урока «Жадный подход» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Жадный подход»?
Выбирайте лучший шаг и не оглядывайтесь назад Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Жадный подход»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Жадный подход
- Выбор активностей по самому раннему завершению
- Дробный рюкзак по соотношению
- Как заметить, что жадный подход не работает