随着人口增长，哪些问题会变得更容易?一个答案是像bittorrent这样的东西，下载速度是节点数量的逆函数。与汽车加载越多速度越慢相反，像bittorrent这样的文件共享网络连接的节点越多速度就越快。

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

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

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

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

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

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

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

正如已经指出的，除了null函数可能的例外，不可能有O(1/n)个函数，因为所花费的时间必须接近0。

当然，有一些算法，比如康拉德定义的算法，它们至少在某种意义上应该小于O(1)

def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

If you want to investigate these algorithms, you should either define your own asymptotic measurement, or your own notion of time. For example, in the above algorithm, I could allow the use of a number of "free" operations a set amount of times. In the above algorithm, if I define t' by excluding the time for everything but the sleep, then t'=1/n, which is O(1/n). There are probably better examples, as the asymptotic behavior is trivial. In fact, I am sure that someone out there can come up with senses that give non-trivial results.

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