algorithms worth knowing

What are some of the most powerful flexible algorithms you use? Stuff that made a big speedup or something.

Here's a cool one I learned for games: buckets: If you wanted to have a screen full of balls that can each bounce off each other then you'd have to do O(N^2) collision tests. So what you do instead of is divide the screen into buckets about double the size of the character; make a linked list of each cell putting the characters into the right buckets then do the collision tests per bucket O(N) since you generally only between 0 and 2 characters in one cell. Let's you have millions of objects when before you could only have a couple thousand.

that's a special case of the n-body problem. Any close enough solution fails the philosophical problem of how the universe solves the true problem.