Fixing Random, part 8

added by DotNetKicks
2/27/2019 1:39:08 PM

1 Kicks, 482 Views

Last time on FAIC we sketched out an O(log n) algorithm for sampling from a weighted distribution of integers by implementing a discrete variation on the "inverse transform" method where the "inverse" step involves a binary search. Can we do better than O(log n)? Yes -- but we'll need an entirely different method.