有没有O(1/n)种算法?

或者其他小于O(1)的数?


当前回答

sharptooth是正确的,O(1)是可能的最佳性能。然而,这并不意味着一个快速的解决方案,只是一个固定时间的解决方案。

一个有趣的变种,也许是真正的建议,是随着人口的增长,哪些问题会变得更容易。我能想出一个虽然是做作的半开玩笑的答案:

一组中有两个人生日相同吗?当n超过365时,返回true。虽然小于365,这是O(nln n)。也许不是一个很好的答案,因为问题不会慢慢变得简单,而是变成O(1)对于n > 365。

其他回答

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

你不能低于O(1)但是O(k) k小于N是可能的。我们称之为次线性时间算法。在某些问题中,次线性时间算法只能给出特定问题的近似解。然而,有时,一个近似解就可以了,可能是因为数据集太大了,或者计算所有数据的计算成本太高了。

有次线性算法。事实上,Bayer-Moore搜索算法就是一个很好的例子。

那么这个呢:

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

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

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

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

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

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