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

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


当前回答

是的。

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

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

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

其他回答

这不可能。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的增加而减少,估计不会改变。

如果根本不运行函数(NOOP)呢?或者使用固定值。这算吗?

我看到一个算法的上限是O(1/n):

由于程序外部的原因(可能是硬件的原因,也可能是处理器中的其他核心的原因),有大量的输入正在发生变化,你必须选择一个随机但有效的输入。

现在,如果它没有变化,你可以简单地列出一个项目列表,随机选择一个,然后得到O(1)次。然而,数据的动态性质使我们无法列出列表,您只能随机探测并测试探测的有效性。(请注意,从本质上讲,不能保证返回时答案仍然有效。这仍然是有用处的——比如游戏中的单位AI。它可以射击在扣动扳机时从视线中消失的目标。)

它的最差情况性能为无穷大,但平均情况性能随着数据空间的填满而下降。

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

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

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

如果解决方案存在,它可以在常数时间=立即准备和访问。例如,如果您知道排序查询是针对倒序的,则使用LIFO数据结构。然后,假设选择了适当的模型(LIFO),数据就已经排序了。