Here, We will discuss about Greedy algorithm, their element and Characteristics, advantages and disadvantages, and their applications.
What is Greedy Algorithm?
A Greedy Algorithm is a simple, intuitive algorithm that is used in optimization problem. It is designed to achieve optimum solution for a given problem.
This algorithm builds up a solution by choosing the option that looks the best at every step.
Greedy algorithm does not always give the best solutions. It works in a top-down approach.
Grredy Algorithm Steps
- To begin with, the solution set (containing solution) is empty.
- At each step, an item is added into the solution set.
- If the solution set is feasible, the current item is kept.
- Else, the item is rejected and never considered again.
Elements of Greedy Algorithms
The two basic properties of optimal Greedy Algorithms are:
- Greedy Choice Property: This property says that optimal solution can be obtained by making a locally optimal solution. The choice made by Greedy algorithm may depend on earlier choices but not on the future.
- Optimal Substructure: A problem show optimal substructure if an optimal solution to the problem contains optimal solution to the subproblems.
Characteristics of Greedy Algorithms
- Used to solve optimization problem.
- Straightforward method to solve a problem.
- Easy to implement.
- Always makes the choice that looks best at the moment
Advantages of Greedy Algorithms
- Easy to understand and code.
- It can perform better than other algorithms.
- Analyzing the run time for greedy algorithm much easier than other techniques.
Disadvantages of Greedy Algorithms
- Does not always give the best solutions.
- Work much harder to understand correctness issues.
Applications of Greedy Algorithms
- Sorting: Selection sort, Topological sort
- Priority Queues: Heap sort
- Huffman coding compression algorithm
- Prism’s and Kruskal’s algorithms
- Shortest path in Weighted Graph
- Coin change problem
- Fractional Knapsack problem
- Job Scheduling algorithm
Want to Contribute:-
If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 [email protected]. See your articles on the main page and help other coders.😎