讨论下算法导论第5章一道概率题

meistudios

好题。我想楼上的算法是对的。
rejection sampling，随机数生成的range是[0..next_pow_of_2(n))，合法段是[0..n)。如果生成的数落在合法段就接受。否则重新sample。
显然最终结果是合法段上的均匀（整数）分布。
期望的接受概率是 n / next_pow_of_2(n)，严格大于1/2.
期望运行的时间是log(n)，也就是log(b -a ).
更具体点是上限 (log2(b - a) + 1) * next_pow_of_2(n) / n * time_of_call_random(0, 1).