有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
如果根本不运行函数(NOOP)呢?或者使用固定值。这算吗?
其他回答
It may be possible to construct an algorithm that is O(1/n). One example would be a loop that iterates some multiple of f(n)-n times where f(n) is some function whose value is guaranteed to be greater than n and the limit of f(n)-n as n approaches infinity is zero. The calculation of f(n) would also need to be constant for all n. I do not know off hand what f(n) would look like or what application such an algorithm would have, in my opinion however such a function could exist but the resulting algorithm would have no purpose other than to prove the possibility of an algorithm with O(1/n).
我不懂数学,但这个概念似乎是寻找一个函数,需要更少的时间,你添加更多的输入?在这种情况下,怎么样:
def f( *args ):
if len(args)<1:
args[1] = 10
当添加可选的第二个参数时,此函数会更快,因为否则必须赋值它。我意识到这不是一个方程,但维基百科页面说大o通常也应用于计算系统。
好吧,我想了一下,也许有一个算法可以遵循这个一般形式:
你需要计算一个1000节点图的旅行商问题,但是,你也有一个你不能访问的节点列表。随着不可访问节点列表的增加,问题变得更容易解决。
我相信量子算法可以通过叠加“一次”进行多次计算……
我怀疑这是一个有用的答案。
这里有另一种方法来证明它:为了拥有一个函数,你必须调用这个函数,并且你必须返回一个答案。这需要固定的时间。即使余下的处理过程对较大的输入花费更少的时间,打印出答案(我们可以假设是单个位)至少需要常数时间。