有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
O(1)仅仅表示“常数时间”。
当你给循环[1]添加一个早期退出时,你(在大O符号中)把一个O(1)算法变成了O(n)算法,但使它更快。
诀窍是一般情况下,常数时间算法是最好的,线性算法比指数算法好,但对于n很小的时候,指数算法可能更快。
1:假设这个例子的列表长度是静态的
其他回答
如果根本不运行函数(NOOP)呢?或者使用固定值。这算吗?
在数值分析中,近似算法在近似公差范围内应具有次常数的渐近复杂度。
class Function
{
public double[] ApproximateSolution(double tolerance)
{
// if this isn't sub-constant on the parameter, it's rather useless
}
}
从我之前学习的大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)。
不,这不可能:
随着n在1/n范围内趋于无穷,我们最终得到1/(无穷),这实际上是0。
因此,问题的大-oh类将是O(0)和一个巨大的n,但更接近常数时间和一个低n。这是不明智的,因为唯一可以在比常数时间更快的时间内完成的事情是:
Void nothing() {};
甚至这也是有争议的!
只要你执行了一个命令,你至少在O(1),所以不,我们不能有一个O(1/n)的大哦类!
如果解决方案存在,它可以在常数时间=立即准备和访问。例如,如果您知道排序查询是针对倒序的,则使用LIFO数据结构。然后,假设选择了适当的模型(LIFO),数据就已经排序了。