在一次采访中，我被要求描述一个函数，给定一个以{names:weights}为输入的对象，该函数可以返回一个随机数。我将被允许使用一个库来生成[0,1]之间的数字，但没有别的。我回答说，这项任务需要分成几个部分:
-
确保权值为累积
[0.25, 0.5, 0.25]->[0.25, 0.75, 1]，保存为c_arr -
生成
[0,1]之间的随机数，保存为val，然后通过for循环迭代我的c_arr。如果val是>如果在c_arr中找到ith元素，则继续，否则返回与ith元素相关联的名称。
我的面试官注意到这是可以接受的，然而，问我是否可以用大O符号表达它的性能。我不是很了解这里，但我回答说它应该是线性的。他回答说这是真的;但是，pseudo可以提高到log(n)时间。
据我所知，log(n)时间意味着不迭代[0,1,2,3,4,5,6,7,8...x]范围内的每个整数，而是像[1,2,4,8,...X]这样的整数。我不确定这是有效的。但即使是这样，我也不确定如何改进伪代码函数，使其不需要以线性方式遍历c_arr中的每个元素。
有人能解释一下吗?
https://softwareengineering.stackexchange.com/questions/150616/get-weighted-random-item/288599
从Orionii皇帝那里偷答案[我没有功劳]:
现在到有趣的部分。这种方法的效率如何?最有效的解决方案是什么?我的这段代码需要O(n)内存，运行时间为O(n)。我不认为它可以在小于O(n)的空间内完成但时间复杂度可以低得多，实际上是O(log n)诀窍是使用二进制搜索而不是常规的for循环。
double r = Random.Next() * totalSum;
int lowGuess = 0;
int highGuess = fruit.Count - 1;
while (highGuess >= lowGuess)
{
int guess = (lowGuess + highGuess) / 2;
if ( csum[guess] < r)
lowGuess = guess + 1;
else if ( csum[guess] - weight[guess] > r)
highGuess = guess - 1;
else
return fruit[guess];
}
还有一个关于更新权重的故事。在最坏的情况下，更新一个元素的权重会导致更新所有元素的累积和，从而使更新复杂度增加到O(n)。这也可以用二叉索引树来简化到O(log n)。