有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
好吧,我想了一下,也许有一个算法可以遵循这个一般形式:
你需要计算一个1000节点图的旅行商问题,但是,你也有一个你不能访问的节点列表。随着不可访问节点列表的增加,问题变得更容易解决。
其他回答
我相信量子算法可以通过叠加“一次”进行多次计算……
我怀疑这是一个有用的答案。
你不能低于O(1)但是O(k) k小于N是可能的。我们称之为次线性时间算法。在某些问题中,次线性时间算法只能给出特定问题的近似解。然而,有时,一个近似解就可以了,可能是因为数据集太大了,或者计算所有数据的计算成本太高了。
我经常用O(1/n)来描述随着输入变大而变小的概率——例如,在log2(n)次投掷中,一枚均匀硬币背面朝上的概率是O(1/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)。
inline void O0Algorithm() {}