如何实现O(1)时空复杂度的带权任务随机选择算法？

问题背景 #

我有一个固定不变的任务列表L，每个任务对应一个整数权重（代表重要性），权重不影响任务排列顺序，但决定被选中的概率——比如权重3和1的两个任务，选中概率分别为75%和25%。

我现在需要实现一种O(1)时空复杂度的随机选择算法，且选择操作会被频繁调用。当前我用的是线性时间方案：

int random = RandomInInterval(0, sumOfL);
foreach(Task T in L){
    random -= T;
    if(random <= 0) return T;
}

这个方法空间复杂度是O(1)，但查询时间是O(n)，想知道有没有O(1)时间的实现方式？

最优解决方案：别名方法（Alias Method） #

这是解决离散加权随机抽样的经典算法，完美匹配你的需求：

• 预处理阶段：仅需一次O(n)时间和空间（列表固定，只执行一次）
• 查询阶段：严格O(1) 时间复杂度，空间维持O(n)（只要任务数量不是极大，这个空间成本完全可接受）

核心逻辑 #

1. 预处理步骤：
   • 先计算所有任务的权重总和，把每个任务的权重转化为概率（权重/总权重）
   • 构建两个数组：
     • Prob数组：每个位置存储对应任务的「直接选中概率」，范围在[0,1]之间
     • Alias数组：每个位置存储另一个任务的索引，用来填补当前任务概率不足1的部分
   • 最终要让每个索引对应的组合结构，刚好满足每个任务的总选中概率等于其权重占比。
2. 查询步骤：
   • 等概率随机生成一个任务索引i（范围0到n-1）
   • 生成一个0到1之间的随机数r
   • 如果r <= Prob[i]，直接选择第i个任务；否则选择Alias[i]对应的任务

每次查询只需要两次随机数生成和一次简单判断，完全是常数时间操作。

概率正确性说明 #

以你提到的例子：任务A权重3，任务B权重1，总权重4。

• A的目标概率是3/4，B是1/4
• 预处理后会构建出等价的概率组合结构，最终查询时，A的总选中概率会严格等于3/4，B等于1/4——本质是别名方法通过数学转换，把加权概率拆解成了「等概率选索引+局部概率判断」的组合，精准还原目标概率。

如果任务数量较多，无需手动实现预处理逻辑，多数编程语言的第三方库已经封装了别名方法的实现，直接调用即可。

其他可选方案（非O(1)，但比线性高效） #

如果暂时不想引入复杂预处理，也可以用前缀和数组+二分查找的方案：

• 预处理阶段：生成前缀和数组（O(n)时间空间）
• 查询阶段：生成0到总权重之间的随机数，用二分查找找到第一个前缀和大于等于该随机数的位置，对应任务就是选中项（O(logn)时间）
  这个方案比线性方法快，但达不到严格O(1)的查询时间，适合对查询时间要求没那么极致的场景。

内容的提问来源于stack exchange，提问作者Daniel