mirror of
https://github.com/krahets/hello-algo.git
synced 2026-07-07 13:14:19 +00:00
krahets
14 lines
4.1 KiB
Markdown
14 lines
4.1 KiB
Markdown
# Резюме
|
|
|
|
### Ключевые моменты
|
|
|
|
- Жадные алгоритмы обычно используются для решения задач оптимизации. Их принцип заключается в том, чтобы на каждом этапе принятия решения делать локально оптимальный выбор в надежде получить глобально оптимальное решение.
|
|
- Жадный алгоритм итеративно делает один жадный выбор за другим, на каждом шаге преобразуя задачу в подзадачу меньшего размера, пока задача не будет решена.
|
|
- Жадные алгоритмы не только просты в реализации, но и обладают высокой эффективностью решения задач. По сравнению с динамическим программированием временная сложность жадных алгоритмов обычно ниже.
|
|
- В задаче о размене монет для некоторых комбинаций монет жадный алгоритм может гарантировать нахождение оптимального решения; для других комбинаций монет это не так, жадный алгоритм может найти очень плохое решение.
|
|
- Задачи, подходящие для решения жадным алгоритмом, обладают двумя основными свойствами: свойством жадного выбора и оптимальной подструктурой. Свойство жадного выбора представляет эффективность жадной стратегии.
|
|
- Для некоторых сложных задач доказательство свойства жадного выбора не является простым. Относительно проще опровергнуть его, например, в задаче о размене монет.
|
|
- Решение жадных задач в основном состоит из трех этапов: анализ задачи, определение жадной стратегии, доказательство корректности. Определение жадной стратегии является ключевым этапом, доказательство корректности часто является сложной задачей.
|
|
- Задача о дробном рюкзаке на основе задачи о рюкзаке 0-1 допускает выбор части предмета, поэтому может быть решена с помощью жадного алгоритма. Корректность жадной стратегии можно доказать методом доказательства от противного.
|
|
- Задача о максимальной вместимости может быть решена методом полного перебора с временной сложностью $O(n^2)$. Разработав жадную стратегию, при которой на каждом шаге перемещается более короткая сторона внутрь, можно оптимизировать временную сложность до $O(n)$.
|
|
- В задаче о максимальном произведении разбиения мы последовательно вывели две жадные стратегии: целые числа $\geq 4$ должны продолжать разбиваться, оптимальный множитель разбиения равен $3$. Код содержит операцию возведения в степень, временная сложность зависит от метода реализации возведения в степень, обычно составляет $O(1)$ или $O(\log n)$. |