Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by acqq on Monday April 04, 2016 @07:19AM
(#11420925)
However note that in the Vitter's paper all discussed algorithms are O(k) as per previous notation, or O(n) using paper's notation where n elements are selected from the set of N:
http://www.ittc.ku.edu/~jsv/Papers/Vit87.RandomSampling.pdf
In short, it's worth reading Vitter's paper, the original post is just a post containing the C code, but the discussion of the algorithm and the comparison with the alternatives is in the paper.
(Edit: corrected the notation of O() as robrenaud suggested)
Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by robrenaud on Monday April 04, 2016 @07:58AM
(#11421151)
Not o (little oh), but rather O (big oh).
There is a difference between them. Little oh roughly means "grows strictly slower than, in the limit", where as big oh roughly means "grows no faster than, in the limit".
http://stackoverflow.com/questions/1364444/difference-betwee...
https://en.wikipedia.org/wiki/Reservoir_sampling )