我看到一个算法的上限是O(1/n):

由于程序外部的原因(可能是硬件的原因，也可能是处理器中的其他核心的原因)，有大量的输入正在发生变化，你必须选择一个随机但有效的输入。

现在，如果它没有变化，你可以简单地列出一个项目列表，随机选择一个，然后得到O(1)次。然而，数据的动态性质使我们无法列出列表，您只能随机探测并测试探测的有效性。(请注意，从本质上讲，不能保证返回时答案仍然有效。这仍然是有用处的——比如游戏中的单位AI。它可以射击在扣动扳机时从视线中消失的目标。)

它的最差情况性能为无穷大，但平均情况性能随着数据空间的填满而下降。

如果解决方案存在，它可以在常数时间=立即准备和访问。例如，如果您知道排序查询是针对倒序的，则使用LIFO数据结构。然后，假设选择了适当的模型(LIFO)，数据就已经排序了。

我相信量子算法可以通过叠加“一次”进行多次计算……

我怀疑这是一个有用的答案。

那么这个呢:

void FindRandomInList(list l)
{
    while(1)
    {
        int rand = Random.next();
        if (l.contains(rand))
            return;
    }
}

随着列表大小的增加，程序的预期运行时间会减少。

O(1/n)并不小于O(1)这基本上意味着你拥有的数据越多，算法运行得越快。假设你有一个数组，如果它小于10100个元素就填充它，如果多于10100个元素就什么都不做。这个当然不是O(1/n)，而是O(-n):)太糟糕了，O大符号不允许负数。

这不可能。Big-O的定义是不大于不平等:

A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)

所以B(n)实际上是最大值，因此如果它随着n的增加而减少，估计不会改变。