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

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


当前回答

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

其他回答

O(1)仅仅表示“常数时间”。

当你给循环[1]添加一个早期退出时,你(在大O符号中)把一个O(1)算法变成了O(n)算法,但使它更快。

诀窍是一般情况下,常数时间算法是最好的,线性算法比指数算法好,但对于n很小的时候,指数算法可能更快。

1:假设这个例子的列表长度是静态的

你不能低于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步(比如检查一个变量,做一个赋值),那也是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)。

随着人口增长,哪些问题会变得更容易?一个答案是像bittorrent这样的东西,下载速度是节点数量的逆函数。与汽车加载越多速度越慢相反,像bittorrent这样的文件共享网络连接的节点越多速度就越快。