algorithm - 反復ランダム加重選択

Question

重みに基づいて、配列からランダムな値を繰り返し選択する方法を見つけようとしています。hereの例を使用しますが、ご了承ください。これは少し異なる質問です。ブローカーを表すクラスは次のとおりです。

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. すべての重みの合計であるサイズの配列を作成し、各ブローカーを配列にa.weights回配置します。次に、0 と新しい配列のサイズの間の数値をランダム化します。ここでの問題 - 前述のように、重みは O(n) であるため、これは O(n^2) アルゴリズムです。
2. これを O(nlog(n)) で解決する方法 (些細なことだと考える人もいるかもしれません) を見つけました。最初のブローカーから前のブローカーまで、各ブローカーに重みの部分的な合計を割り当てます。次に、0 から重みの合計までの数字を描き、二分探索でブローカーを見つけます。バランスの取れた二分探索木を使用してこれを達成することもできました。

より良い (つまり、O(n)、または O(log(log(n)))) ソリューションを知っている人はいますか? またはそれ以外の場合 - O(nlog(n)) よりも高速に実行できないことを証明できる人はいますか?