Algorithms
Greedy Algorithms
Цели урока
- Understand the greedy algorithm paradigm
- Know the correctness conditions
- Solve classic problems
- Distinguish Greedy from DP
Предварительные знания
- MST (examples of greedy)
Greed is one of the seven deadly sins. But in algorithms, greed sometimes leads to a perfect result! Dijkstra, Huffman, Prim - they are all greedy.
- Data compression (Huffman, LZW)
- Task scheduling
- Routing (Dijkstra)
- Network protocols (MST)
From Huffman codes to the theory of matroids
Greedy algorithms existed long before anyone explained why they work. In 1952 David Huffman, a graduate student at MIT, was given a choice between a final exam and a term paper on optimal prefix codes. He chose the paper and found the optimal greedy construction now called Huffman coding, which beat the method his own professor Robert Fano had used. Joseph Kruskal (1956) and Robert Prim (1957) gave greedy algorithms for minimum spanning trees. The deep question was when a greedy choice is guaranteed to be optimal. The answer came from matroid theory: in 1971 Jack Edmonds proved that the greedy algorithm finds the optimum exactly when the problem's structure forms a matroid. That result turned greedy from a lucky heuristic into a paradigm with a precise correctness condition.
Idea: Local Optimum
**A greedy algorithm** makes the locally optimal choice at each step, hoping to reach a global optimum.
**Greedy doesn't always work!** For coins [1, 3, 4] and amount 6: greedy gives 4+1+1=3 coins, but optimal is 3+3=2 coins.
**When greedy works:**
- **Greedy choice property:** an optimal solution includes the greedy choice
- **Optimal substructure:** after the choice, the remaining problem has the same form
- **No rollback:** the choice cannot be revisited later
Coins [1, 5, 6], amount 10. Greedy gives:
Proving Correctness
**Two ways to prove that greedy works:**
**Example: Activity Selection**
**If you can't prove it - greedy may not work!** Always look for a counterexample.
For Activity Selection, why can't you pick the interval with minimum START?
Classic Examples
**1. Activity Selection (interval scheduling):**
**2. Fractional Knapsack:**
**3. Huffman Coding:**
| Problem | Greedy strategy | Complexity |
|---|---|---|
| Activity Selection | Min end time | O(n log n) |
| Fractional Knapsack | Max value/weight | O(n log n) |
| Huffman Coding | Min frequency merge | O(n log n) |
| Dijkstra | Min distance vertex | O((V+E) log V) |
| Prim/Kruskal MST | Min edge weight | O(E log E) |
0/1 Knapsack (no fractions allowed) - does greedy work?
Greedy vs Dynamic Programming
| Greedy | DP | |
|---|---|---|
| Approach | Locally optimal choice | All subproblems |
| Proof | Exchange / Stays Ahead | Optimal substructure |
| Complexity | Usually O(n log n) | Usually O(n²) or O(n×W) |
| Coin Change (standard) | ✓ Works | Not needed |
| Coin Change (arbitrary) | ✗ Doesn't work | ✓ Needed |
| 0/1 Knapsack | ✗ Doesn't work | ✓ Needed |
| Fractional Knapsack | ✓ Works | Overkill |
**When to suspect DP is needed:**
- 'Minimum number of operations'
- 'How many ways'
- '0/1 choice' (take it or not)
- 'Optimal partition'
'Minimum number of jumps to reach the end of the array' - this is:
Greedy Algorithms
- Locally optimal choice → global (sometimes)
- A correctness proof is required!
- Exchange Argument / Stays Ahead
- Usually faster than DP
- If fractions are allowed - probably Greedy
Related Topics
Greedy is often an alternative to DP.
- Dynamic Programming — When Greedy doesn't work
- MST — Kruskal and Prim are greedy
- Dijkstra — Greedy choice of nearest vertex
Связанные уроки
- alg-17-mst — MST greedy choices motivate the greedy paradigm
- alg-14-dijkstra — Dijkstra greedily picks the nearest frontier vertex
- alg-21-dp — When greedy fails, DP guarantees the global optimum
- mm-04-second-order
- ml-31-transformers