有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
是的。
只有一种算法运行时为O(1/n),即“空”算法。
对于O(1/n)的算法来说,这意味着它渐进地执行的步骤比由单个指令组成的算法少。如果对于所有n个> n0,它执行的步骤少于1步,则对于这n个,它必须完全不包含任何指令。由于检查' If n > n0'至少需要1条指令,因此对于所有n个,它必须不包含任何指令。
总结: 唯一的算法是O(1/n)是空算法,不包含任何指令。
其他回答
inline void O0Algorithm() {}
我相信量子算法可以通过叠加“一次”进行多次计算……
我怀疑这是一个有用的答案。
这里有另一种方法来证明它:为了拥有一个函数,你必须调用这个函数,并且你必须返回一个答案。这需要固定的时间。即使余下的处理过程对较大的输入花费更少的时间,打印出答案(我们可以假设是单个位)至少需要常数时间。
那么这个呢:
void FindRandomInList(list l)
{
while(1)
{
int rand = Random.next();
if (l.contains(rand))
return;
}
}
随着列表大小的增加,程序的预期运行时间会减少。
你不能低于O(1)但是O(k) k小于N是可能的。我们称之为次线性时间算法。在某些问题中,次线性时间算法只能给出特定问题的近似解。然而,有时,一个近似解就可以了,可能是因为数据集太大了,或者计算所有数据的计算成本太高了。