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

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


当前回答

不,这不可能:

随着n在1/n范围内趋于无穷,我们最终得到1/(无穷),这实际上是0。

因此,问题的大-oh类将是O(0)和一个巨大的n,但更接近常数时间和一个低n。这是不明智的,因为唯一可以在比常数时间更快的时间内完成的事情是:

Void nothing() {};

甚至这也是有争议的!

只要你执行了一个命令,你至少在O(1),所以不,我们不能有一个O(1/n)的大哦类!

其他回答

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

好吧,我想了一下,也许有一个算法可以遵循这个一般形式:

你需要计算一个1000节点图的旅行商问题,但是,你也有一个你不能访问的节点列表。随着不可访问节点列表的增加,问题变得更容易解决。

没有比O(1)小的数 大o符号表示算法的最大复杂度

如果一个算法的运行时间是n³+ n²+ n + 5那么它就是O(n³) 低次在这里根本不重要,因为n ->正无穷,n^2与n^3相比是无关的

同样地,当n -> Inf时,O(1/n)与O(1)相比是不相关的,因此3 + O(1/n)将与O(1)相同,从而使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的增加而减少,估计不会改变。

这是一个简单的O(1/n)算法。它甚至做了一些有趣的事情!

function foo(list input) {
  int m;
  double output;

  m = (1/ input.size) * max_value;  
  output = 0;
  for (int i = 0; i < m; i++)
    output+= random(0,1);

  return output;
}

O(1/n) is possible as it describes how the output of a function changes given increasing size of input. If we are using the function 1/n to describe the number of instructions a function executes then there is no requirement that the function take zero instructions for any input size. Rather, it is that for every input size, n above some threshold, the number of instructions required is bounded above by a positive constant multiplied by 1/n. As there is no actual number for which 1/n is 0, and the constant is positive, then there is no reason why the function would constrained to take 0 or fewer instructions.