Difference between Greedy Algorithm and Divide and Conquer Algorithm
Divide and conquer Algorithm:
Divide and Conquer is an algorithmic paradigm in which the problem is solved using the Divide, Conquer, and Combine strategy.
A typical Divide and Conquer algorithm solves a problem using the following three steps:
- 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.
Greedy Algorithm:
Greedy algorithm is defined as a method for solving optimization problems by taking decisions that result in the most evident and immediate benefit irrespective of the final outcome. It is a simple, intuitive algorithm that is used in optimization problems.
Difference between the Greedy Algorithm and the Divide and Conquer Algorithm:
| Sl.No |
Divide and conquer |
Greedy Algorithm |
|---|---|---|
|
1 |
Divide and conquer is used to obtain a solution to the given problem, it does not aim for the optimal solution. | The greedy method is used to obtain an optimal solution to the given problem. |
|
2 |
In this technique, the problem is divided into small subproblems. These subproblems are solved independently. Finally, all the solutions to subproblems are collected together to get the solution to the given problem. | In Greedy Method, a set of feasible solutions are generated and pick up one feasible solution is the optimal solution. |
|
3 |
Divide and conquer is less efficient and slower because it is recursive in nature. | A greedy method is comparatively efficient and faster as it is iterative in nature. |
|
4 |
Divide and conquer may generate duplicate solutions. | In the Greedy method, the optimal solution is generated without revisiting previously generated solutions, thus it avoids the re-computation |
|
5 |
Divide and conquer algorithms mostly run in polynomial time. | Greedy algorithms also run in polynomial time but take less time than Divide and conquer |
|
6 |
Examples: Merge sort, Quick sort, Strassen’s matrix multiplication. |
Examples: Fractional Knapsack problem, Activity selection problem, Job sequencing problem. |
Divide and conquer Algorithm:
Divide and Conquer is an algorithmic paradigm in which the problem is solved using the Divide, Conquer, and Combine strategy.
A typical Divide and Conquer algorithm solves a problem using the following three steps:
- 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.
Greedy Algorithm:
Greedy algorithm is defined as a method for solving optimization problems by taking decisions that result in the most evident and immediate benefit irrespective of the final outcome. It is a simple, intuitive algorithm that is used in optimization problems.
Difference between the Greedy Algorithm and the Divide and Conquer Algorithm:
| Sl.No |
Divide and conquer |
Greedy Algorithm |
|---|---|---|
|
1 |
Divide and conquer is used to obtain a solution to the given problem, it does not aim for the optimal solution. | The greedy method is used to obtain an optimal solution to the given problem. |
|
2 |
In this technique, the problem is divided into small subproblems. These subproblems are solved independently. Finally, all the solutions to subproblems are collected together to get the solution to the given problem. | In Greedy Method, a set of feasible solutions are generated and pick up one feasible solution is the optimal solution. |
|
3 |
Divide and conquer is less efficient and slower because it is recursive in nature. | A greedy method is comparatively efficient and faster as it is iterative in nature. |
|
4 |
Divide and conquer may generate duplicate solutions. | In the Greedy method, the optimal solution is generated without revisiting previously generated solutions, thus it avoids the re-computation |
|
5 |
Divide and conquer algorithms mostly run in polynomial time. | Greedy algorithms also run in polynomial time but take less time than Divide and conquer |
|
6 |
Examples: Merge sort, Quick sort, Strassen’s matrix multiplication. |
Examples: Fractional Knapsack problem, Activity selection problem, Job sequencing problem. |
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.