将循环的线性时间转换为 log(n) 时间函数？

Question

在一次采访中，我被要求描述一个函数，该函数可以 return 一个随机数给定一个对象 {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 元素，则继续，否则 return 与 ith 元素关联的名称。

我的面试官指出这是可以接受的，但是，问我是否可以使用大 O 表示法阐明其性能。我在这里不是很了解，但回答说应该是线性时间。他回答说这是真的；但是，伪函数可以改进到 log(n) 时间。

据我所知，log(n) 时间意味着不会遍历 [0,1,2,3,4,5,6,7,8...x] 范围内的每个整数，而是遍历 [1,2,4,8,...X] 之类的东西。我不确定这是否经过验证。但即使是这样，我也不确定如何改进伪代码功能，使其不需要以线性方式遍历 c_arr 中的每个元素。

有人可以解释一下吗？

Answer 1

https://softwareengineering.stackexchange.com/questions/150616/get-weighted-random-item/288599

窃取奥里奥尼皇帝的答案[我不相信]:

现在进入有趣的部分。这种方法的效率如何？什么是最有效的解决方案？我的一段代码需要 O(n) 内存和 O(n) 时间的运行。我不认为它可以用少于 O(n) space 来完成，但时间复杂度可以低得多，实际上是 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)。

将循环的线性时间转换为 log(n) 时间函数？

Turning a linear time for loop into a log(n) time function?

random

big-o

loops

probability