A greedy algorithm is a simple and efficient algorithmic approach for solving any given problem by selecting the best available option at that moment of time, without bothering about the future results.
The most basic purpose of greedy algorithm is optimization which can be either minimization or maximization based on our problem statement requirements.
Greedy algorithms have several advantages over other algorithmic approaches:
- Greedy algorithms are often easier to describe and code up than other algorithms.
- Greedy algorithms can often be implemented more efficiently than other algorithms.
Though greedy algorithm doesn’t provide correct solution in some cases, it is known that this algorithm works for the majority of problems.
As greedy algorithm is fast and efficient, it is used in many other most commonly used algorithms such as:
Huffman Coding:
It is the most common algorithm in the field of data compression. It analyzes a given message and based on the frequencies of the characters present in the message, a variable-length code for each symbol is assigned.
Dijkstra’s Algorithm:
It is the most famous graph traversal one that is used for finding the shortest path between nodes in a graph.
Minimal Spanning Tree (MST):
It is widely used in Cluster Analysis, Handwriting recognition and Image segmentation.
The time complexity of a greedy algorithm depends on what problem to be solved and what is the data structure used to represent the problem.
The time complexity will be O(n log n) for unsorted activities and O(n) for sorted activities.
Sometimes greedy algorithms fail to find the globally optimal solution because they do not consider all the data. The choice made by a greedy algorithm may depend on choices it has made so far, but it is not aware of future choices it could make.