0

我试图找出一种方法来根据它们的权重从数组中迭代地选择随机值。我将使用此处的示例，但请耐心等待-这是一个略有不同的问题。这是一个代表经纪人的类：

public class Broker
{
    public string Name = string.Empty;
    public int Weight = 0;

    public Broker(string n, int w)
    {
        this.Name = n;
        this.Weight = w;
    }
}

现在，我有一个代理数组，我想随机选择一个代理，使得要选择的代理a的概率等于a.Weight除以数组中所有权重的总和。

这里的变化是我想这样做n 次，其中n 是数组的大小。所以我们可以在开始之前稍微处理一下这些数字（它不会少于 O(n)）。另请注意，权重与 n 的数量级相同。

这是我到目前为止想到的方向

  1. 构建一个大小为所有权重之和的数组，并将每个 Broker a.weights次放入数组中 - 然后随机化一个介于 0 和新数组大小之间的数字。这里的问题 - 如前所述，权重是 O(n)，因此这是一个 O(n^2) 算法。
  2. 我找到了一种在 O(nlog(n)) 中解决这个问题的方法（有些人可能认为这是微不足道的）。我为每个经纪人分配部分权重总和，从第一个经纪人到前一个经纪人。然后我从 0 到权重之和画一个数字，并通过二分搜索找到经纪人。我也可以通过平衡二叉搜索树来实现这一点。

有谁知道更好的（即 O(n)，甚至 O(log(log(n)))）解决方案？或者以其他方式 - 谁能证明我们不能比 O(nlog(n)) 更快地做到这一点？

4

0 回答 0