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

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


当前回答

我不知道算法,但复杂度小于O(1)出现在随机算法中。实际上,o(1)(小o)小于o(1)这种复杂性通常出现在随机算法中。例如,如你所说,当某个事件的概率为1/n阶时,他们用o(1)表示。或者当他们想说某件事发生的概率很高时(例如1 - 1/n),他们用1 - o(1)表示。

其他回答

那么这个呢:

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

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

随着人口增长,哪些问题会变得更容易?一个答案是像bittorrent这样的东西,下载速度是节点数量的逆函数。与汽车加载越多速度越慢相反,像bittorrent这样的文件共享网络连接的节点越多速度就越快。

inline void O0Algorithm() {}

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

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

如果不管输入数据如何,答案都是一样的,那么你就有一个O(0)算法。

或者换句话说——在提交输入数据之前,答案就已经知道了 -这个功能可以优化-所以O(0)