What is greedy algorithm ?
Author: neptune | 08th-Jun-2022
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, and when we can use the technique i.e Greedy algorithm.
What is a Greedy algorithm?
A Greedy Algorithm always makes the choice that looks best at the moment. We make the locally optimal choice in the hope that it will lead us to the global optimal solution.
Where can we use the Greedy algorithm?
The Greedy method is quite powerful and works well for a wide range of problems. We can use the Greedy algorithm whenever we have to either maximize or minimize the problem.
We use Greedy method in the following algorithms:
1. Minimum-spanning-tree algorithm
2. Dijkstra Algorithm
3. Huffman Data-compression
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 disadvantages 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 ranges of problems. Many algorithms can be viewed as applications of the Greedy algorithms, a 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!!!
#JavaScript #Hackerrank #Python #Motivation #AI #React.js #Testing #Interview #SQL #Selenium #LeetCode #Problem Solving #Machine learning #Java #GPT #AWS #API #IT #Algorithms #Github #Jobs #Microservice #Certifications #Projects #Google #Django #Story #Pip #Data Science #Postman #Health #Twitter #Elon Musk #Node.js
Top 8 Algorithms every programmer should Know !!!Author: neptune | 21st-Apr-2023
#Algorithms
The top 8 algorithms for programmers include sorting, searching, graph, dynamic programming, greedy, divide and conquer, backtracking, and randomized...
Problem of Merging Two Sorted Linked ListsAuthor: neptune | 02nd-Jun-2023
#Algorithms #Problem Solving
Merging two sorted linked lists efficiently into a single, sorted list can be achieved using optimized algorithms...
View More
anonymous | May 11, 2022, 12:09 a.m.
Well explained 👍