Объясните что такое "жадный алгоритм" и когда такой подход целесообразно использовать.

Можете назвать потенциальные места или задачи использования такого подхода на бэкенд-приложения?

Подсказки:

• Учтите, чем жадные алгоритмы отличаются от подходов динамического программирования или разделяй и властвуй.
• Подумайте о задачах, где принятие локально оптимального решения приводит к глобально оптимальному решению.
• Примеры могут включать планирование задач с дедлайнами, сжатие файлов или протоколы маршрутизации сети.
• Учтите ограничения жадных алгоритмов и когда они могут не найти оптимальное решение.

Выше ожиданий:

• Понимание техник доказательства жадных алгоритмов, таких как аргументы обмена.
• Способность анализировать компромиссы между временной и пространственной сложностью по сравнению с другими алгоритмическими подходами

Жадные алгоритмы (greedy algorithm) принимают решения, выбирая вариант, который кажется наилучшим в текущий момент, не рассматривая всю область задачи. На каждом шаге он выбирает локально оптимальное решение в надежде найти глобальный оптимум.

Ключевые характеристики

• Делает локально оптимальный выбор на каждом этапе
• Никогда не пересматривает предыдущие решения
• Обычно прост в реализации и эффективен
• В многих случаях выполняется за время O(n log n) (часто встречается в сортировке)

Когда подходят жадные алгоритмы

Алгоритмы жадности хорошо работают, когда задачи обладают:

1. Свойством жадного выбора: локально оптимальный выбор приводит к глобально оптимальному решению
2. Оптимальной подструктурой: оптимальные решения содержат оптимальные подрешения

Сравнение с другими подходами

  Динамическое программирование   vs      Жадные алгоритмы
┌────────────────────────────────┐  ┌─────────────────────────────────┐
│ • Рассматривает все возможные  │  │ • Делает один выбор и никогда   │
│   выборы                       │  │   не смотрит назад              │
│ • Кэширует результаты, чтобы   │  │ • Простой и понятный            │
│   избежать перерасчёта         │  │ • Часто сложность O(n log n)    │
│ • Часто сложность O(n²)        │  │                                 │
└────────────────────────────────┘  └─────────────────────────────────┘

Сценарий бэкенда: планирование задач

Рассмотрим планировщик задач бэкенда, управляющий API-запросами с различными временами обработки и приоритетами. Каждый запрос имеет:

• Время обработки (t)
• Значение приоритета (p)
• Отношение приоритета к времени (p/t)

Жадный подход: отсортировать запросы по отношению приоритета к времени в порядке убывания и обработать их в этом порядке.

Это максимизирует системную ценность, обрабатывая сначала задачи высокого приоритета и быстрые задачи. Этот подход обеспечивает оптимальные решения, когда цель состоит в максимизации общей ценности без взаимозависимостей между задачами.

Ограничения

Алгоритмы жадности терпят неудачу, когда:

• Задача требует учета будущих последствий, например данные будут переиспользованы для точного ответа
• Локальная оптимальность не приводит к глобальной оптимальности
• Задача имеет ограничения, которые влияют на предыдущие решения

Например, в задаче о рюкзаке с неделимыми предметами жадный подход, выбирающий предметы по отношению стоимости к весу, не гарантирует оптимального решения.