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

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


当前回答

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

其他回答

从我之前学习的大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)。

sharptooth是正确的,O(1)是可能的最佳性能。然而,这并不意味着一个快速的解决方案,只是一个固定时间的解决方案。

一个有趣的变种,也许是真正的建议,是随着人口的增长,哪些问题会变得更容易。我能想出一个虽然是做作的半开玩笑的答案:

一组中有两个人生日相同吗?当n超过365时,返回true。虽然小于365,这是O(nln n)。也许不是一个很好的答案,因为问题不会慢慢变得简单,而是变成O(1)对于n > 365。

有次线性算法。事实上,Bayer-Moore搜索算法就是一个很好的例子。

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

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

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

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

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