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

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


当前回答

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

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

其他回答

正如已经指出的,除了null函数可能的例外,不可能有O(1/n)个函数,因为所花费的时间必须接近0。

当然,有一些算法,比如康拉德定义的算法,它们至少在某种意义上应该小于O(1)

def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

If you want to investigate these algorithms, you should either define your own asymptotic measurement, or your own notion of time. For example, in the above algorithm, I could allow the use of a number of "free" operations a set amount of times. In the above algorithm, if I define t' by excluding the time for everything but the sleep, then t'=1/n, which is O(1/n). There are probably better examples, as the asymptotic behavior is trivial. In fact, I am sure that someone out there can come up with senses that give non-trivial results.

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

这不可能。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)但是O(k) k小于N是可能的。我们称之为次线性时间算法。在某些问题中,次线性时间算法只能给出特定问题的近似解。然而,有时,一个近似解就可以了,可能是因为数据集太大了,或者计算所有数据的计算成本太高了。

从我之前学习的大O符号来看,即使你需要1步(比如检查一个变量,做一个赋值),那也是O(1)。

注意,O(1)和O(6)是一样的,因为“常数”并不重要。这就是为什么O(n)和O(3n)是一样的。

如果你需要1步,那就是O(1)。因为你的程序至少需要1步,所以算法的最小值是O(1)。除非我们不这样做,那么它是O(0),对吧?如果我们做任何操作,那么它就是O(1)这是它能达到的最小值。

(如果我们选择不这样做,那么它可能成为一个禅宗或道的问题……在编程领域,O(1)仍然是最小值)。

或者这样怎么样:

程序员:老板,我找到了一个在O(1)时间内完成的方法! 老板:没必要,今天早上我们就要破产了。 程序员:哦,那么它就变成了O(0)。