是否有O（1 / n）算法？

Question

是否有O（1 / n）算法？还是其他小于O（1）的东西？

Answer 1

这个问题并不像看起来那样愚蠢。至少从理论上讲，当我们采用Big O符号的数学定义时，诸如O（1 / n）之类的东西是完全明智的：

现在您可以轻松地将g（x）替换为1 / x …显然上述定义对于f仍然成立。

为了估计渐近运行时的增长，这种方法不太可行……有意义的算法无法随着输入的增长而更快。当然，您可以构造一个任意算法来实现这一目标，例如以下算法：

def get_faster(list):

    how_long = (1 / len(list)) * 100000

    sleep(how_long)

显然，随着输入大小的增加，此函数花费的时间更少……至少要达到一定的限制（由硬件强制执行）（数字的精度，sleep可以等待的最短时间，处理参数的时间等）：然后，此限制为恒定下界所以其实上述功能仍然具有运行时Ô（1）。

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

Answer 2

是。

恰好有一种运行时为O（1 / n）的算法，即“空”算法。

对于O（1 / n）算法，意味着它比由单个指令组成的算法以更少的步长渐近执行。如果所有n> n0的执行步数少于一个步骤，则对于所有n，它必须完全不包含任何指令。由于检查“如果n> n0”花费至少1条指令，因此对于所有n，它必须不包含任何指令。

总结：唯一的算法为O（1 / n）是空算法，不包含任何指令。

Answer 3

根据我以前对大O表示法的了解，即使您需要1个步骤（例如检查变量，执行赋值），也就是O（1）。

注意，O（1）与O（6）相同，因为“常数”无关紧要。这就是为什么我们说O（n）与O（3n）相同。

因此，即使您只需要1步，也就是O（1）...，并且由于您的程序至少需要1步，因此算法可以执行的最小值为O（1）。除非我们不这样做，否则我认为它是O（0）？如果我们什么都不做，那就是O（1），这是它可以经过的最小值。

（如果我们选择不这样做，那么它可能会成为Zen或Tao问题……在编程领域，O（1）仍然是最小值）。

还是这样：

程序员：老板，我找到了一种在O（1）时间内做到的方法！

老板：没必要这样做，我们今天早上破产了。

程序员：哦，那变成O（0）。