Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
Опубликовано: 14 Февраля, 2023
Разделяй и властвуй Алгоритм:
Разделяй и властвуй — это алгоритмическая парадигма, в которой задача решается с помощью стратегии «Разделяй, властвуй и комбинируй».
Типичный алгоритм «разделяй и властвуй» решает проблему, используя следующие три шага:
- Divide: This involves dividing the problem into smaller sub-problems.
- Conquer: Solve sub-problems by calling recursively until solved.
- Combine: Combine the sub-problems to get the final solution of the whole problem.
Жадный алгоритм:
Жадный алгоритм определяется как метод решения задач оптимизации путем принятия решений, которые приводят к наиболее очевидной и непосредственной выгоде независимо от конечного результата . Это простой, интуитивно понятный алгоритм, который используется в задачах оптимизации.
Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»:
| Сл.№ | Разделяй и властвуй | Жадный алгоритм |
|---|---|---|
1 | Разделяй и властвуй используется для получения решения данной проблемы, а не для достижения оптимального решения. | Жадный метод используется для получения оптимального решения поставленной задачи. |
2 | В этом методе проблема разбивается на небольшие подзадачи. Эти подзадачи решаются независимо. Наконец, все решения подзадач собираются вместе, чтобы получить решение данной проблемы. | В жадном методе генерируется набор допустимых решений, и выбирается одно из возможных решений, которое является оптимальным решением. |
3 | Принцип «разделяй и властвуй» менее эффективен и медленнее, потому что он рекурсивен по своей природе. | Жадный метод сравнительно эффективен и быстрее, поскольку он итеративный по своей природе. |
4 | Разделяй и властвуй может привести к дублированию решений. | В жадном методе оптимальное решение генерируется без повторного просмотра ранее сгенерированных решений, что позволяет избежать повторного вычисления. |
5 | Алгоритмы «разделяй и властвуй» обычно выполняются за полиномиальное время. | Жадные алгоритмы также работают за полиномиальное время, но требуют меньше времени, чем разделяй и властвуй. |
6 | Примеры: сортировка слиянием, Быстрая сортировка, Умножение матриц Штрассена. | Примеры: задача о дробном рюкзаке, Проблема выбора деятельности, Проблема последовательности выполнения заданий. |