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

### Related:

No post found!

*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.