在数值分析中，近似算法在近似公差范围内应具有次常数的渐近复杂度。

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}

这里有另一种方法来证明它:为了拥有一个函数，你必须调用这个函数，并且你必须返回一个答案。这需要固定的时间。即使余下的处理过程对较大的输入花费更少的时间，打印出答案(我们可以假设是单个位)至少需要常数时间。

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).

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

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

是的。

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

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

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

你不能低于O(1)但是O(k) k小于N是可能的。我们称之为次线性时间算法。在某些问题中，次线性时间算法只能给出特定问题的近似解。然而，有时，一个近似解就可以了，可能是因为数据集太大了，或者计算所有数据的计算成本太高了。