3 ms·
The Alias Method is an O(1) algorithm to select elements from a distribution
- pgsandstrom 14y ago"You could also use ranges, picking a random number between 0.0 and 1.0 and returning :win when the number is below 0.8, :lose otherwise. But, these algorithms are still O(n)" Maybe my math is a bit rusty, but is this really O(n)? Why is that?
- andreer 14y agon here is the number of different elements you can choose from. If there was a third alternative, you'd have to add another if statement.
- filpen 14y agoWhile looking up Walker's Alias Method I ended up here http://forums.udacity.com/questions/1012915/resampling-walker-alias-method http://forums.udacity.com/questions/1012915/resampling-walke... , where people say it is not Walker's method, but Vode's. I can't verify it right now but I thought it might be of interest anyway.
- andreer 14y agoAn excellent writeup on different techniques to do this: http://www.keithschwarz.com/darts-dice-coins/ http://www.keithschwarz.com/darts-dice-coins/