有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
随着人口增长,哪些问题会变得更容易?一个答案是像bittorrent这样的东西,下载速度是节点数量的逆函数。与汽车加载越多速度越慢相反,像bittorrent这样的文件共享网络连接的节点越多速度就越快。
其他回答
我相信量子算法可以通过叠加“一次”进行多次计算……
我怀疑这是一个有用的答案。
你不能低于O(1)但是O(k) k小于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的增加而减少,估计不会改变。
我看到一个算法的上限是O(1/n):
由于程序外部的原因(可能是硬件的原因,也可能是处理器中的其他核心的原因),有大量的输入正在发生变化,你必须选择一个随机但有效的输入。
现在,如果它没有变化,你可以简单地列出一个项目列表,随机选择一个,然后得到O(1)次。然而,数据的动态性质使我们无法列出列表,您只能随机探测并测试探测的有效性。(请注意,从本质上讲,不能保证返回时答案仍然有效。这仍然是有用处的——比如游戏中的单位AI。它可以射击在扣动扳机时从视线中消失的目标。)
它的最差情况性能为无穷大,但平均情况性能随着数据空间的填满而下降。
O(1/n)并不小于O(1)这基本上意味着你拥有的数据越多,算法运行得越快。假设你有一个数组,如果它小于10100个元素就填充它,如果多于10100个元素就什么都不做。这个当然不是O(1/n),而是O(-n):)太糟糕了,O大符号不允许负数。