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

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


当前回答

不,这不可能:

随着n在1/n范围内趋于无穷,我们最终得到1/(无穷),这实际上是0。

因此,问题的大-oh类将是O(0)和一个巨大的n,但更接近常数时间和一个低n。这是不明智的,因为唯一可以在比常数时间更快的时间内完成的事情是:

Void nothing() {};

甚至这也是有争议的!

只要你执行了一个命令,你至少在O(1),所以不,我们不能有一个O(1/n)的大哦类!

其他回答

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

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

我不知道算法,但复杂度小于O(1)出现在随机算法中。实际上,o(1)(小o)小于o(1)这种复杂性通常出现在随机算法中。例如,如你所说,当某个事件的概率为1/n阶时,他们用o(1)表示。或者当他们想说某件事发生的概率很高时(例如1 - 1/n),他们用1 - o(1)表示。

在数值分析中,近似算法在近似公差范围内应具有次常数的渐近复杂度。

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}

我看到一个算法的上限是O(1/n):

由于程序外部的原因(可能是硬件的原因,也可能是处理器中的其他核心的原因),有大量的输入正在发生变化,你必须选择一个随机但有效的输入。

现在,如果它没有变化,你可以简单地列出一个项目列表,随机选择一个,然后得到O(1)次。然而,数据的动态性质使我们无法列出列表,您只能随机探测并测试探测的有效性。(请注意,从本质上讲,不能保证返回时答案仍然有效。这仍然是有用处的——比如游戏中的单位AI。它可以射击在扣动扳机时从视线中消失的目标。)

它的最差情况性能为无穷大,但平均情况性能随着数据空间的填满而下降。

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