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

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


当前回答

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

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

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

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

其他回答

这里有另一种方法来证明它:为了拥有一个函数,你必须调用这个函数,并且你必须返回一个答案。这需要固定的时间。即使余下的处理过程对较大的输入花费更少的时间,打印出答案(我们可以假设是单个位)至少需要常数时间。

好吧,我想了一下,也许有一个算法可以遵循这个一般形式:

你需要计算一个1000节点图的旅行商问题,但是,你也有一个你不能访问的节点列表。随着不可访问节点列表的增加,问题变得更容易解决。

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

这不可能。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的增加而减少,估计不会改变。

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