Approximation algorithms
- Algorithms course
- Expert
- Lesson 9/41
- 4 min
Polynomial-time approximate solutions.
Approximation algorithms
NP-complete problems require exponential time for exact solutions. An approximation algorithm produces a quality but not exact solution in acceptable time.
Approximation ratio measures how close the solution is to optimum. For example, a 2-approximation algorithm gives at most twice worse results.
Finding the maximum
Finding the largest element of an array is a simple starting point for approximation algorithms. Linear scan gives exact solution in O(n).
This example shows the 'good solution' concept underlying approximation algorithms. We will examine approximate and random methods in later steps.
Practice find_max function
Write find_max(arr). Return the largest element of the array. Print 9 with print(find_max([3, 5, 7, 1, 9])).
Starter code
def find_max(arr):
# Find the largest elementSample solution
def find_max(arr):
# Find the largest element
best = arr[0]
for i in range(1, len(arr)):
if arr[i] > best:
best = arr[i]
return best
print(find_max([3, 5, 7, 1, 9]))Expected output
9
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What does an approximation algorithm provide?
- Exact solution
- Fast and close solution Correct answer
- No solution
- Random solution
Explanation: Approximation gives a fast and close solution.
2 Finding max
best = arr[____]best = arr[0]Explanation: 0 is right.
3 Approximation algorithms: match the terms
| Term | Meaning |
|---|---|
approximation |
Approximate |
ratio |
Ratio |
NP-complete |
Hard |
fast |
O(n) |