Method
approximation
Articles
PAR
Technique
Greedy algorithms
The best step now with no looking back: when it is optimal, when almost, and how to prove it.
usually O(n log n): a sort or a heap
2 problems
NUM~
Algorithm
Bisection and Newton's method
A root of an equation: halving an interval is reliable, Newton's tangents are fast.
bisection: log₂((b − a)/ε) steps; Newton: about log₂ of the number of digits
2 problems
NUM~
Algorithm
Gradient descent
Finds the minimum of a function by steps against the gradient, in the direction of steepest descent.
O(κ · log(1/ε)) steps
2 problems
Often together
classic 3 interviews 3 optimization 2 geodata 2 iterative 2 science and physics 2 greedy 1 scheduling 1 heap 1 contests 1 root finding 1 binary search 1