mirror of
https://github.com/krahets/hello-algo.git
synced 2026-06-16 15:18:37 +08:00
772183705e
* Add Russian docs site baseline * Add Russian localized codebase * Polish Russian code wording * Update ru code translation. * Update code translation and chapter covers. * Fix pythontutor extraction. * Add README and landing page. * placeholder of profiles * Use figures of English version * Remove chapter paperbook
15 lines
3.9 KiB
Markdown
15 lines
3.9 KiB
Markdown
# Резюме
|
||
|
||
### Ключевые моменты
|
||
|
||
- Жадный алгоритм обычно используется для решения задач оптимизации. Его принцип состоит в том, чтобы на каждом этапе принятия решения делать локально оптимальный выбор в надежде получить глобально оптимальный ответ.
|
||
- Жадный алгоритм итеративно делает один жадный выбор за другим, на каждом шаге превращая задачу в подзадачу меньшего размера, пока задача не будет полностью решена.
|
||
- Жадный алгоритм не только прост в реализации, но и часто обладает высокой эффективностью. По сравнению с динамическим программированием его временная сложность обычно ниже.
|
||
- В задаче о размене монет для некоторых наборов монет жадный алгоритм способен гарантировать оптимальный ответ, а для других наборов - нет: он может дать очень плохое решение.
|
||
- Задачи, подходящие для жадного алгоритма, обладают двумя ключевыми свойствами: свойством жадного выбора и оптимальной подструктурой. Свойство жадного выбора отражает корректность жадной стратегии.
|
||
- Для некоторых сложных задач доказать свойство жадного выбора непросто. Относительно легче найти контрпример и опровергнуть его, как это видно на примере задачи о размене монет.
|
||
- Решение жадной задачи обычно состоит из трех шагов: анализ задачи, определение жадной стратегии и доказательство корректности. Из них ключевым является выбор жадной стратегии, а доказательство корректности часто оказывается самым трудным.
|
||
- В задаче о дробном рюкзаке, в отличие от задачи о рюкзаке 0-1, разрешено брать часть предмета, поэтому ее можно решать жадным алгоритмом. Корректность жадной стратегии доказывается методом от противного.
|
||
- Задачу о максимальной вместимости можно решать полным перебором со временной сложностью $O(n^2)$. Разработав жадную стратегию со сдвигом короткой перегородки внутрь на каждом шаге, временную сложность можно оптимизировать до $O(n)$.
|
||
- В задаче о максимальном произведении разбиения мы последовательно выводим две жадные стратегии: все целые числа $\geq 4$ следует дальше разбивать, а оптимальным множителем разбиения является $3$. В коде присутствуют операции возведения в степень, поэтому временная сложность зависит от способа их реализации и обычно равна $O(1)$ или $O(\log n)$.
|