Re:Ask HN: What's the most interesting algorithm?
by kele on Sunday May 08, 2016 @10:47AM
(#11654242)
The union-find data structure (the idea is so simple and a sophisticated analysis yields a really low upper bound).
RMQ with linear preprocessing and constant time queries (which is also true for multi-dimensional cases, if the dimension is bounded by a constant).
Knuth-Morris-Pratt pattern matching is the first algorithm where I saw the usage of an additional variable in the pseudocode just to simplify the complexity analysis.
RMQ with linear preprocessing and constant time queries (which is also true for multi-dimensional cases, if the dimension is bounded by a constant).
Knuth-Morris-Pratt pattern matching is the first algorithm where I saw the usage of an additional variable in the pseudocode just to simplify the complexity analysis.