What is greedy algorithm ?

Author: neptune | 29th-May-2021 | views: 44

In the programming world, there is no such technique that solves all computation problems. We need to apply various kinds of techniques for various problems. Some commonly used techniques are-

  1. Divide and conquer

  2. Randomized algorithms

  3. Greedy algorithms 

  4. Dynamic programming

Note: Greedy is a technique, not an algorithm.

Here we are going to understand what, where, how, when we used technique i.e Greedy algorithm. 

What is a Greedy algorithm?

A greedy algorithm, as we know greedy means intense and selfish desire to something. To solve a problem we make choices that look best at that time. This expects that we make a locally-optimal choice in the hope that it leads us to a globally-optimal solution. 

Where we can use Greedy algorithm?

We can use Greedy algorithm whenever we have to either maximize or minimize the problem. 

Basic Structure of a Greedy algorithm.

Optimal_greedy_fun(Item, arr[], int n)

  1) Initialize empty result : result = ()  

  2) While (Iterate for all values)

      // Make your greedy choice to select item.

      i = SelectAnItem() 

      // If i is feasible, add i to the result

      if (feasible(i))

        result = result U i 

      // finally return result 

  3) return result

How do you decide which choice is optimal?

There are mostly two kinds of problems in optimization maximization or minimization. Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. 

A Greedy algorithm makes greedy choices at each level of computation to ensure that the objective function is optimized. It has only one chance to compute the optimal solution, it never gets back to the previous decision.

Advantages and disadvantage of Greedy algorithm:

  1. When we solve an optimization problem first we came up with a Greedy solution.

  2. Compare to other algorithms run time analysis of greedy is easier than others like divide and Conquer.

  3. The disadvantage of Greedy is that it is very hard to prove that your solution and algorithm are correct.

Note: Most greedy algorithms are not optimized and correct.

Application of Greedy algorithm.

The greedy method is quite powerful and works well for various range of problems. Many algorithms can be viewed as applications of the Greedy algorithms, few of them are:

  1. Minimum Spanning Tree.

  2. Dijkstra’s algorithm for finding the shortest paths from a single source.

  3. Huffman codes (for Data compression).

Thanks for reading.


Related Blogs
Related Blogs View More