这是一个简单的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.

我相信量子算法可以通过叠加“一次”进行多次计算……

我怀疑这是一个有用的答案。

这不可能。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)是不可能的。算法所花费的任何时间都称为O(1)。但是对于O(1/n)下面的函数呢。(我知道这个解决方案中已经出现了许多变体，但我猜它们都有一些缺陷(不是主要的，它们很好地解释了这个概念)。这里有一个，只是为了方便讨论:

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

因此，随着n的增加，函数将花费越来越少的时间。此外，如果输入实际为0，则函数将永远返回。

有人可能会说，这将受到机器精度的限制。因此，由于c eit有一个上界，它是O(1)。但我们也可以绕过它，通过在字符串中输入n和C。加法和比较是对字符串进行的。用这个方法，我们可以把n减小到任意小。因此，即使忽略n = 0，函数的上限也是无界的。

我也相信我们不能说运行时间是O(1/n)。我们应该写成O(1 + 1/n)

O(1/n)并不小于O(1)这基本上意味着你拥有的数据越多，算法运行得越快。假设你有一个数组，如果它小于10100个元素就填充它，如果多于10100个元素就什么都不做。这个当然不是O(1/n)，而是O(-n):)太糟糕了，O大符号不允许负数。

我经常用O(1/n)来描述随着输入变大而变小的概率——例如，在log2(n)次投掷中，一枚均匀硬币背面朝上的概率是O(1/n)。