3 ms·
Bogosort is always a fun one, because I think its one of the better introductions to NP-complete problems. If you imagine that there's no "easy" algorithm to r
by dragontamer 5y ago
Bogosort is always a fun one, because I think its one of the better introductions to NP-complete problems.
If you imagine that there's no "easy" algorithm to return a sorted list (but sorted lists do exist), then the only methodology possible is to try all combinations. And you do this either systematically, or randomly.
Random NP-complete algorithms, such as WalkSAT, are quite good in practice. Systematic NP-complete algorithms, such as DPLL-SAT, are more "obvious" in how they work, and are sufficient for smaller sizes.