3 ms·
In a similar vein, almost every algorithm can be converted into a O(1) space version simply by converting it into the dumbest possible search algorithm over the
by skulk 6y ago
In a similar vein, almost every algorithm can be converted into a O(1) space version simply by converting it into the dumbest possible search algorithm over the solution space: just sample from the solution space randomly (with a seeded PRNG or something) until you get the right answer.
A well-known example of this is bogosort: https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort
- teraflop 6y agoInterestingly, bogosort cannot actually be implemented in constant space -- at least, not if you're talking about a deterministic algorithm. In order for your PRNG to have a large enough state space to cover all possible permutations, it needs O(n log n) bits. In the Turing machine model of computation, algorithms that use O(1) space are theoretically equivalent to finite state machines (potentially with a very large number of states). Logarithmic space is where things start to get interesting, because it's enough to store a constant number of pointers into an arbitrarily large input.