正如已经指出的，除了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.

是的。

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

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

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

sharptooth是正确的，O(1)是可能的最佳性能。然而，这并不意味着一个快速的解决方案，只是一个固定时间的解决方案。

一个有趣的变种，也许是真正的建议，是随着人口的增长，哪些问题会变得更容易。我能想出一个虽然是做作的半开玩笑的答案:

一组中有两个人生日相同吗?当n超过365时，返回true。虽然小于365，这是O(nln n)。也许不是一个很好的答案，因为问题不会慢慢变得简单，而是变成O(1)对于n > 365。

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

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

大o符号表示算法与典型运行时不同的最坏情况。证明O(1/n)算法是O(1)算法很简单。根据定义, O(1/n)——> T(n) <= 1/n, for all n >= C > 0 O (1 / n)——> T (n) < = 1 / C,因为1 / n <所有n > = 1 / C = C O(1/n)——> O(1)，因为大O符号忽略常数(即C的值无关紧要)

这个问题并不像有些人认为的那样愚蠢。至少在理论上，当我们采用大O符号的数学定义时，像O(1/n)这样的东西是完全合理的:

现在你可以很容易地用g(x)代替1/x……很明显，上面的定义对于某个f仍然成立。

为了估计渐近运行时增长的目的，这是不太可行的……一个有意义的算法不能随着输入的增长而变得更快。当然，你可以构造一个任意的算法来实现这一点，例如下面这个:

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

显然，随着输入大小的增长，这个函数花费的时间更少，至少直到硬件强制的某个限制(数字的精度，睡眠可以等待的最小时间，处理参数的时间等):这个限制将是一个常数下界，因此实际上上面的函数仍然有运行时O(1)。

但实际上，在现实世界中，当输入大小增加时，运行时可能会减少(至少部分减少)。但是请注意，这些算法不会在O(1)以下表现出运行时行为。不过，它们还是很有趣的。以Horspool的非常简单的文本搜索算法为例。在这里，期望运行时将随着搜索模式长度的增加而减少(但是增加草堆长度将再次增加运行时)。