concept · INFO-CS-ADS-160Greedy Algorithms
A greedy algorithm constructs a solution step by step by choosing the option that appears best at the current stage. Once a choice is made, it is usually not reconsidered. Greedy algorithms can be efficient and simple, but they produce globally optimal solutions only when the problem has suitable mathematical properties, particularly the greedy-choice property and optimal substructure.
Explanation
Overview
A greedy algorithm is an algorithmic strategy that repeatedly selects a locally optimal choice according to a defined rule, aiming to construct a globally optimal solution.
Time complexity
There is no universal complexity for greedy algorithms. Many require sorting followed by a linear scan, giving O(n log n), while graph-based algorithms have complexities that depend on their data structures.
Space complexity
Space usage depends on the implementation. Some greedy algorithms use O(1) auxiliary space after sorting, while graph algorithms may require O(V + E) storage.
Applications
Designing and implementing solutions involving greedy algorithms.; Teaching and assessing greedy algorithms in computer-science courses and interviews.; Checking solutions that use greedy algorithms against correctness and resource constraints.
Advantages
Often simple to implement.; Can be highly efficient.; Usually makes decisions without exploring every possible solution.; Can use relatively little memory.; Works especially well for problems with a provable greedy-choice property.
Limitations
A locally optimal choice may prevent a globally optimal result.; Many optimization problems do not satisfy the greedy-choice property.; Choices are usually not reconsidered after commitment.; Correctness can require a careful mathematical proof.; A greedy solution may be only approximate when no optimality guarantee exists.
Common mistakes
Assuming the largest immediate benefit always leads to the best final solution.; Using a greedy strategy without proving its correctness.; Confusing feasibility with optimality.; Applying a rule from one problem to a different problem without justification.; Ignoring restrictions such as non-negative edge weights in Dijkstra's algorithm.
Example or application
A worked example has not yet been added.
Definition
A greedy algorithm is an algorithmic strategy that repeatedly selects a locally optimal choice according to a defined rule, aiming to construct a globally optimal solution.
Core Principle
At each decision point, choose the best available option according to the greedy rule, commit to that choice, and continue until the solution is complete.
Working Process
Identify the set of available choices.
Define a rule for ranking or selecting choices.
Select the locally best available choice.
Check whether the choice is feasible under the problem's constraints.
Commit to the choice if it is valid.
Repeat until the solution is complete.
Important Properties
| Property | Description |
|---|
Greedy-choice property | A globally optimal solution can be constructed by making an appropriate locally optimal choice first. |
Optimal substructure | An optimal solution contains optimal solutions to the relevant subproblems created after a choice. |
Examples
| Algorithm | Description | Result |
|---|
Activity Selection | Repeatedly select the compatible activity that finishes earliest. | Produces a maximum-size compatible set of activities under the standard assumptions. |
Kruskal's Algorithm | Repeatedly select the lowest-weight edge that does not create a cycle. | Constructs a minimum spanning tree for a connected weighted undirected graph. |
Prim's Algorithm | Repeatedly add the minimum-weight edge connecting the current tree to a new vertex. | Constructs a minimum spanning tree for a connected weighted undirected graph. |
Dijkstra's Algorithm | Repeatedly finalizes the unvisited vertex with the smallest tentative distance. | Finds shortest paths from a source when all edge weights are non-negative. |
Huffman Coding | Repeatedly combines the two least-frequent symbols or subtrees. | Constructs an optimal prefix code under the standard frequency-based model. |
Simple Example
Problem
Select the maximum number of mutually compatible activities.
Activities
| Name | Start | Finish |
|---|
A | 1 | 3 |
B | 2 | 5 |
C | 4 | 6 |
D | 6 | 8 |
Strategy
Sort activities by finishing time and select an activity whenever its start time is not earlier than the finish time of the previously selected activity.
Explanation
Choosing the earliest-finishing compatible activity leaves as much remaining time as possible for later activities.
Correctness Requirements
The greedy selection rule must be justified for the particular problem.
Every selected choice must satisfy the problem's constraints.
The remaining subproblem must preserve the structure needed for an optimal solution.
A proof must establish that making the greedy choice does not exclude every globally optimal solution.
Time Complexity
There is no universal complexity for greedy algorithms. Many require sorting followed by a linear scan, giving O(n log n), while graph-based algorithms have complexities that depend on their data structures.
Space Complexity
Space usage depends on the implementation. Some greedy algorithms use O(1) auxiliary space after sorting, while graph algorithms may require O(V + E) storage.
Advantages
Often simple to implement.
Can be highly efficient.
Usually makes decisions without exploring every possible solution.
Can use relatively little memory.
Works especially well for problems with a provable greedy-choice property.
Limitations
A locally optimal choice may prevent a globally optimal result.
Many optimization problems do not satisfy the greedy-choice property.
Choices are usually not reconsidered after commitment.
Correctness can require a careful mathematical proof.
A greedy solution may be only approximate when no optimality guarantee exists.
Common Mistakes
Assuming the largest immediate benefit always leads to the best final solution.
Using a greedy strategy without proving its correctness.
Confusing feasibility with optimality.
Applying a rule from one problem to a different problem without justification.
Ignoring restrictions such as non-negative edge weights in Dijkstra's algorithm.
Learning Tip
Test a proposed greedy rule on small examples and try to construct a counterexample. If it fails, examine whether dynamic programming or another strategy is needed.
Applications
Designing and implementing solutions involving greedy algorithms.
Teaching and assessing greedy algorithms in computer-science courses and interviews.
Checking solutions that use greedy algorithms against correctness and resource constraints.
Practice Questions
| Question | Answer |
|---|
What is the main purpose of greedy algorithms? | A greedy algorithm constructs a solution step by step by choosing the option that appears best at the current stage. Once a choice is made, it is usually not reconsidered. Greedy algorithms can be efficient and simple, but they produce globally optimal solutions only when the problem has suitable mathematical properties, particularly the greedy-choice property and optimal substructure. |
What should be checked before applying greedy algorithms? | For greedy algorithms, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of greedy algorithms be validated? | Trace a representative greedy algorithms case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of greedy algorithms.
Identify the assumptions, inputs, and conditions relevant to greedy algorithms.
Evaluate an application of greedy algorithms for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures