这个问题的最有效算法

Question

我已经提出了几个解决方案，但我认为它们的效率不高，而且我很难计算它们的复杂性。

计划A）对于我随机选择的[1,N]范围内的每一个整数，我检查它是否被占用。如果是，我重新滚动直到我得到一个未被占用的整数。这对于N的高阶数来说变得低效，因为碰撞非常高。

计划B）每次迭代时，我遍历数组的所有值，那些我没有占用的我会写在一个列表中。之后，我洗牌列表（例如通过Fisher-Yates shuffle？）并任意获得第一个对象。这不是空间效率，对于我的问题，我不能只保留一个列表并从那里洗牌，因为在我的程序中可能有多个线程计算这个。

计划C）计划A的一点变化：我在[1,N]范围内随机选择，我检查它是否被占用。如果是，我+1并尝试下一个，如果是，再次+1。最坏的情况是所有数组插槽都被占用，除了一个->O(N)。

有没有更好的办法来解决这个问题？这个具体的问题是我的软件中一个非常重要的模块，所以时间复杂度是至关重要的。如果没有，你认为我应该选择哪种方式（对于那些有计算时间复杂度天赋的人）。谢谢你！

Answer 1

我建议你同时采用A和B两种方案。

使用，直到数组大部分填充完毕。然后搜索未使用的索引，将它们放入一个数组，并使用计划B。您必须对您的约束进行试验，以确定何时切换。

但是，您关于多线程执行此操作的评论是令人关切的。请注意，当多个线程访问同一内存时，竞争情况很容易发生，争用访问权限会减慢您的速度。