时间戳

首页 > 解决方案 > 将循环的线性时间转换为 log(n) 时间函数？

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

问题描述

在一次采访中，我被要求描述一个函数，它可以返回一个给定对象的随机数{names:weights}作为输入。我将被允许使用库来生成介于两者之间的数字，[0,1]但仅此而已。我回答说任务需要分解为：

  1. 确保权重是累积的[0.25, 0.5, 0.25]-> [0.25, 0.75, 1]，保存为c_arr

  2. [0,1]在另存为 a之间产生一个随机数，然后通过for 循环val遍历我的。c_arr如果val是 > 中的ith元素c_arr，则继续，否则返回与该ith元素关联的名称。

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

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

有人可以解释一下吗？

标签： loopsrandombig-oprobability

解决方案

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)。

推荐阅读