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-
Divide and conquer
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.
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.
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
result = result U i
// finally return result
3) return result
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.
When we solve an optimization problem first we came up with a Greedy solution.
Compare to other algorithms run time analysis of greedy is easier than others like divide and Conquer.
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.
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:
Minimum Spanning Tree.
Dijkstra’s algorithm for finding the shortest paths from a single source.
Huffman codes (for Data compression).
Thanks for reading.