3 ms·
Well, if all you care about is the space complexity you could do the same thing with 8 bytes of memory, an integer and a floating point. Start the floating poin
by EvanMiller 15y ago
Well, if all you care about is the space complexity you could do the same thing with 8 bytes of memory, an integer and a floating point. Start the floating point at zero. For each item, set the integer to 0, then compare the item to every other item (including itself) and add one to the integer if they are equal. After each iteration, add one divided by the integer to the floating point, and repeat for the next item. When you're done the answer will be stored in the floating point.
Of course this method requires O(N^2) time (that is, 1,000,000,000,000,000,000 compare operations when counting a billion objects), but who cares? It only uses 8 bytes!
- colanderman 15y agoUhh, beside that I don't get what's going on with the floating point number in your algorithm, that requires storing the N items, which is exactly what the author is trying to avoid.
- subleq 15y agoIf you're allowed to make multiple passes over your set, you might as apply an in-place comparison sort and get it down to O(n*log n) time with constant space. Their method has the advantage that the stream doesn't need to be stored -- events can be processed as they come in and then discarded, never storing the entire set.
- nitrogen 15y agoIf n is large enough (and 1000000000 definitely is), at some point (possibly even the beginning) adding 1/n to the floating point value will result in no change.