hello-algo/ru/docs/chapter_greedy/summary.md

Резюме

Ключевые моменты

• Жадные алгоритмы обычно используются для решения задач оптимизации. Их принцип заключается в том, чтобы на каждом этапе принятия решения делать локально оптимальный выбор в надежде получить глобально оптимальное решение.
• Жадный алгоритм итеративно делает один жадный выбор за другим, на каждом шаге преобразуя задачу в подзадачу меньшего размера, пока задача не будет решена.
• Жадные алгоритмы не только просты в реализации, но и обладают высокой эффективностью решения задач. По сравнению с динамическим программированием временная сложность жадных алгоритмов обычно ниже.
• В задаче о размене монет для некоторых комбинаций монет жадный алгоритм может гарантировать нахождение оптимального решения; для других комбинаций монет это не так, жадный алгоритм может найти очень плохое решение.
• Задачи, подходящие для решения жадным алгоритмом, обладают двумя основными свойствами: свойством жадного выбора и оптимальной подструктурой. Свойство жадного выбора представляет эффективность жадной стратегии.
• Для некоторых сложных задач доказательство свойства жадного выбора не является простым. Относительно проще опровергнуть его, например, в задаче о размене монет.
• Решение жадных задач в основном состоит из трех этапов: анализ задачи, определение жадной стратегии, доказательство корректности. Определение жадной стратегии является ключевым этапом, доказательство корректности часто является сложной задачей.
• Задача о дробном рюкзаке на основе задачи о рюкзаке 0-1 допускает выбор части предмета, поэтому может быть решена с помощью жадного алгоритма. Корректность жадной стратегии можно доказать методом доказательства от противного.
• Задача о максимальной вместимости может быть решена методом полного перебора с временной сложностью O(n^2). Разработав жадную стратегию, при которой на каждом шаге перемещается более короткая сторона внутрь, можно оптимизировать временную сложность до O(n).
• В задаче о максимальном произведении разбиения мы последовательно вывели две жадные стратегии: целые числа \geq 4 должны продолжать разбиваться, оптимальный множитель разбиения равен 3. Код содержит операцию возведения в степень, временная сложность зависит от метода реализации возведения в степень, обычно составляет O(1) или O(\log n).