21 lines
2.1 KiB
Markdown
21 lines
2.1 KiB
Markdown
#алгоритмы #поиск
|
||
|
||
> Жадный алгоритм прост: на каждом шаге он выбирает оптимальный вариант. В технической терминологии: на каждом шаге выбирается локально-оптимальное решение, а в итоге вы получаете глобально-оптимальное решение.
|
||
|
||
Жадная стратегия не дает оптимального решения. Впрочем, результат не так уж далек от оптимума. В некоторых случаях достаточно алгоритма, способного решить задачу достаточно хорошо. И в таких областях жадные алгоритмы работают отлично, потому что они просто реализуются, а полученное решение обычно близко к оптимуму.
|
||
|
||
|
||
### Приближенные алгоритмы
|
||
|
||
|
||
Когда вычисление точного решения занимает слишком много времени, применяется приближенный алгоритм. Эффективность приближенного алгоритма оценивается по:
|
||
- быстроте;
|
||
- близости полученного решения к оптимальному.
|
||
|
||
Жадные алгоритмы хороши не только тем, что они обычно легко формулируются, но и тем, что простота обычно оборачивается скоростью выполнения. В данном случае жадный алгоритм выполняется за время $O(n^2)$
|
||
|
||
Жадный алгоритм не всегда даст точный ответ, но он очень быстр. Задача о покрытии множеств относится к NP-трудным задачам.
|
||
|
||
|
||
Источники:
|
||
- [[Адитья Бхаргава - Грокаем Алгоритмы]] |