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

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


当前回答

我不懂数学,但这个概念似乎是寻找一个函数,需要更少的时间,你添加更多的输入?在这种情况下,怎么样:

def f( *args ): 
  if len(args)<1:
    args[1] = 10

当添加可选的第二个参数时,此函数会更快,因为否则必须赋值它。我意识到这不是一个方程,但维基百科页面说大o通常也应用于计算系统。

其他回答

这个问题并不像有些人认为的那样愚蠢。至少在理论上,当我们采用大O符号的数学定义时,像O(1/n)这样的东西是完全合理的:

现在你可以很容易地用g(x)代替1/x……很明显,上面的定义对于某个f仍然成立。

为了估计渐近运行时增长的目的,这是不太可行的……一个有意义的算法不能随着输入的增长而变得更快。当然,你可以构造一个任意的算法来实现这一点,例如下面这个:

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

显然,随着输入大小的增长,这个函数花费的时间更少,至少直到硬件强制的某个限制(数字的精度,睡眠可以等待的最小时间,处理参数的时间等):这个限制将是一个常数下界,因此实际上上面的函数仍然有运行时O(1)。

但实际上,在现实世界中,当输入大小增加时,运行时可能会减少(至少部分减少)。但是请注意,这些算法不会在O(1)以下表现出运行时行为。不过,它们还是很有趣的。以Horspool的非常简单的文本搜索算法为例。在这里,期望运行时将随着搜索模式长度的增加而减少(但是增加草堆长度将再次增加运行时)。

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

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

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

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

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

It may be possible to construct an algorithm that is O(1/n). One example would be a loop that iterates some multiple of f(n)-n times where f(n) is some function whose value is guaranteed to be greater than n and the limit of f(n)-n as n approaches infinity is zero. The calculation of f(n) would also need to be constant for all n. I do not know off hand what f(n) would look like or what application such an algorithm would have, in my opinion however such a function could exist but the resulting algorithm would have no purpose other than to prove the possibility of an algorithm with O(1/n).

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

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