4 ms·
Anyone know the name of this algorithm? There is a similarly solved classic problem in complexity theory: Given an O(m) list of O(n)-bounded integers, determi
by shasta 16y ago
Anyone know the name of this algorithm? There is a similarly solved classic problem in complexity theory: Given an O(m) list of O(n)-bounded integers, determine if there are duplicates in O(m) time and O(n) space.
- ori_b 16y agoI don't know if it has a name (it seems to simply be referred to as "an efficient sparse set representation"), but I think I initially remember seeing it introduced in "Compilers: Principles, Techniques, and Tools" in an exercise at some point in the past. A good description of it is here: http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html http://research.swtch.com/2008/03/using-uninitialized-memory...