The random (or drunkard's) walk is a great, simple algorithm that can generate very organic-looking maps, such as this:
Unfortunately it seems to have poor scalability, making it unsuitable for generating large maps in a reasonable amount of time. For example, a test I performed looking at how many iterations are required to generate a desired range for a 1D random walk yielded what looked like quadratic complexity:
Range | Iterations
------+-----------
10 | 81
100 | 7309
1000 | 585352
10000 | 30656784
For higher-dimension walks I imagine this would be even worse.
How can improve the efficiency of random walk, whilst preserving the overall look of the result, for large maps? I'm hoping for a solution with sub-quadratic complexity.