有没有O（1 / n）算法？
有没有O（1 / n）算法？
或者小于O（1）的其他任何东西？
这个问题并不像看起来那么愚蠢。 至少在理论上，当我们对大O符号进行数学定义时，诸如O（1 / n）之类的东西是完全合理的：
现在你可以很容易地用g（x）代替1 / x ...很明显，上面的定义对于某些f仍然适用。
为了估计渐近运行时间增长，这是不太可行的......随着输入增长，一个有意义的算法无法变得更快。 当然，你可以构造一个任意的算法来完成这个任务，例如下面的算法：
def get_faster(list):
how_long = (1 / len(list)) * 100000
sleep(how_long)
显然，随着输入大小的增长，这个函数花费的时间会更少......至少在某些限制之前，硬件会强制执行（数字的精度， sleep可以等待的最少时间，处理参数的时间等）：这个限制将会是一个恒定的下限，所以实际上上述函数仍然具有运行时O（1）。
但实际上有一些真实世界的算法，其中运行时可以在输入大小增加时减少（至少部分）。 请注意，虽然这些算法不会在O（1）之下显示运行时行为。 不过，它们很有趣。 例如，Horspool采用非常简单的文本搜索算法。 在这里，随着搜索模式长度的增加，预期的运行时间会减少（但增加草垛长度会再次增加运行时间）。
是。
运行时O（1 / n）恰好有一种算法，即“空”算法。
对于算法是O（1 / n）意味着它执行渐近地执行比由单个指令组成的算法更少的步骤。 如果所有n> n0的执行次数少于一步，则对于那些n必须完全没有指令。 由于检查'if n> n0'是否至少需要1条指令，它必须包含对所有n的指令。
总结：唯一的算法是O（1 / n）是空算法，由无指令组成。
这是不可能的。 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的增加而减小，则估计不会改变。
链接地址: http://www.djcxy.com/p/40071.html