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

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


当前回答

大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(1/n)并不小于O(1)这基本上意味着你拥有的数据越多,算法运行得越快。假设你有一个数组,如果它小于10100个元素就填充它,如果多于10100个元素就什么都不做。这个当然不是O(1/n),而是O(-n):)太糟糕了,O大符号不允许负数。

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

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

我看到一个算法的上限是O(1/n):

由于程序外部的原因(可能是硬件的原因,也可能是处理器中的其他核心的原因),有大量的输入正在发生变化,你必须选择一个随机但有效的输入。

现在,如果它没有变化,你可以简单地列出一个项目列表,随机选择一个,然后得到O(1)次。然而,数据的动态性质使我们无法列出列表,您只能随机探测并测试探测的有效性。(请注意,从本质上讲,不能保证返回时答案仍然有效。这仍然是有用处的——比如游戏中的单位AI。它可以射击在扣动扳机时从视线中消失的目标。)

它的最差情况性能为无穷大,但平均情况性能随着数据空间的填满而下降。

大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的值无关紧要)