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

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


当前回答

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

其他回答

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

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

O(1)仅仅表示“常数时间”。

当你给循环[1]添加一个早期退出时,你(在大O符号中)把一个O(1)算法变成了O(n)算法,但使它更快。

诀窍是一般情况下,常数时间算法是最好的,线性算法比指数算法好,但对于n很小的时候,指数算法可能更快。

1:假设这个例子的列表长度是静态的

如果根本不运行函数(NOOP)呢?或者使用固定值。这算吗?

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