有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
这不可能。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的增加而减少,估计不会改变。
其他回答
不,这不可能:
随着n在1/n范围内趋于无穷,我们最终得到1/(无穷),这实际上是0。
因此,问题的大-oh类将是O(0)和一个巨大的n,但更接近常数时间和一个低n。这是不明智的,因为唯一可以在比常数时间更快的时间内完成的事情是:
Void nothing() {};
甚至这也是有争议的!
只要你执行了一个命令,你至少在O(1),所以不,我们不能有一个O(1/n)的大哦类!
那么这个呢:
void FindRandomInList(list l)
{
while(1)
{
int rand = Random.next();
if (l.contains(rand))
return;
}
}
随着列表大小的增加,程序的预期运行时间会减少。
我不懂数学,但这个概念似乎是寻找一个函数,需要更少的时间,你添加更多的输入?在这种情况下,怎么样:
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)是空算法,不包含任何指令。
我相信量子算法可以通过叠加“一次”进行多次计算……
我怀疑这是一个有用的答案。