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

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


当前回答

是的。

只有一种算法运行时为O(1/n),即“空”算法。

对于O(1/n)的算法来说,这意味着它渐进地执行的步骤比由单个指令组成的算法少。如果对于所有n个> n0,它执行的步骤少于1步,则对于这n个,它必须完全不包含任何指令。由于检查' If n > n0'至少需要1条指令,因此对于所有n个,它必须不包含任何指令。

总结: 唯一的算法是O(1/n)是空算法,不包含任何指令。

其他回答

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

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

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

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

我不懂数学,但这个概念似乎是寻找一个函数,需要更少的时间,你添加更多的输入?在这种情况下,怎么样:

def f( *args ): 
  if len(args)<1:
    args[1] = 10

当添加可选的第二个参数时,此函数会更快,因为否则必须赋值它。我意识到这不是一个方程,但维基百科页面说大o通常也应用于计算系统。

是的。

只有一种算法运行时为O(1/n),即“空”算法。

对于O(1/n)的算法来说,这意味着它渐进地执行的步骤比由单个指令组成的算法少。如果对于所有n个> n0,它执行的步骤少于1步,则对于这n个,它必须完全不包含任何指令。由于检查' If n > n0'至少需要1条指令,因此对于所有n个,它必须不包含任何指令。

总结: 唯一的算法是O(1/n)是空算法,不包含任何指令。