有没有O(1/n)种算法?

或者其他小于O(1)的数?


当前回答

我经常用O(1/n)来描述随着输入变大而变小的概率——例如,在log2(n)次投掷中,一枚均匀硬币背面朝上的概率是O(1/n)。

其他回答

如果解决方案存在,它可以在常数时间=立即准备和访问。例如,如果您知道排序查询是针对倒序的,则使用LIFO数据结构。然后,假设选择了适当的模型(LIFO),数据就已经排序了。

有次线性算法。事实上,Bayer-Moore搜索算法就是一个很好的例子。

这个问题并不像有些人认为的那样愚蠢。至少在理论上,当我们采用大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的非常简单的文本搜索算法为例。在这里,期望运行时将随着搜索模式长度的增加而减少(但是增加草堆长度将再次增加运行时)。

我猜小于O(1)是不可能的。算法所花费的任何时间都称为O(1)。但是对于O(1/n)下面的函数呢。(我知道这个解决方案中已经出现了许多变体,但我猜它们都有一些缺陷(不是主要的,它们很好地解释了这个概念)。这里有一个,只是为了方便讨论:

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

因此,随着n的增加,函数将花费越来越少的时间。此外,如果输入实际为0,则函数将永远返回。

有人可能会说,这将受到机器精度的限制。因此,由于c eit有一个上界,它是O(1)。但我们也可以绕过它,通过在字符串中输入n和C。加法和比较是对字符串进行的。用这个方法,我们可以把n减小到任意小。因此,即使忽略n = 0,函数的上限也是无界的。

我也相信我们不能说运行时间是O(1/n)。我们应该写成O(1 + 1/n)

我不懂数学,但这个概念似乎是寻找一个函数,需要更少的时间,你添加更多的输入?在这种情况下,怎么样:

def f( *args ): 
  if len(args)<1:
    args[1] = 10

当添加可选的第二个参数时,此函数会更快,因为否则必须赋值它。我意识到这不是一个方程,但维基百科页面说大o通常也应用于计算系统。