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

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


当前回答

如果不管输入数据如何,答案都是一样的,那么你就有一个O(0)算法。

或者换句话说——在提交输入数据之前,答案就已经知道了 -这个功能可以优化-所以O(0)

其他回答

我相信量子算法可以通过叠加“一次”进行多次计算……

我怀疑这是一个有用的答案。

不,这不可能:

随着n在1/n范围内趋于无穷,我们最终得到1/(无穷),这实际上是0。

因此,问题的大-oh类将是O(0)和一个巨大的n,但更接近常数时间和一个低n。这是不明智的,因为唯一可以在比常数时间更快的时间内完成的事情是:

Void nothing() {};

甚至这也是有争议的!

只要你执行了一个命令,你至少在O(1),所以不,我们不能有一个O(1/n)的大哦类!

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

我不知道算法,但复杂度小于O(1)出现在随机算法中。实际上,o(1)(小o)小于o(1)这种复杂性通常出现在随机算法中。例如,如你所说,当某个事件的概率为1/n阶时,他们用o(1)表示。或者当他们想说某件事发生的概率很高时(例如1 - 1/n),他们用1 - o(1)表示。

我猜小于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)