有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有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大符号不允许负数。