有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
这不可能。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的增加而减少，估计不会改变。
其他回答
我相信量子算法可以通过叠加“一次”进行多次计算……
我怀疑这是一个有用的答案。
不，这不可能:
随着n在1/n范围内趋于无穷，我们最终得到1/(无穷)，这实际上是0。
因此，问题的大-oh类将是O(0)和一个巨大的n，但更接近常数时间和一个低n。这是不明智的，因为唯一可以在比常数时间更快的时间内完成的事情是:
Void nothing() {};
甚至这也是有争议的!
只要你执行了一个命令，你至少在O(1)，所以不，我们不能有一个O(1/n)的大哦类!
如果不管输入数据如何，答案都是一样的，那么你就有一个O(0)算法。
或者换句话说——在提交输入数据之前，答案就已经知道了 -这个功能可以优化-所以O(0)
这不可能。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的增加而减少，估计不会改变。
随着人口增长，哪些问题会变得更容易?一个答案是像bittorrent这样的东西，下载速度是节点数量的逆函数。与汽车加载越多速度越慢相反，像bittorrent这样的文件共享网络连接的节点越多速度就越快。
