有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
那么这个呢:
void FindRandomInList(list l)
{
while(1)
{
int rand = Random.next();
if (l.contains(rand))
return;
}
}
随着列表大小的增加,程序的预期运行时间会减少。
其他回答
我不懂数学,但这个概念似乎是寻找一个函数,需要更少的时间,你添加更多的输入?在这种情况下,怎么样:
def f( *args ):
if len(args)<1:
args[1] = 10
当添加可选的第二个参数时,此函数会更快,因为否则必须赋值它。我意识到这不是一个方程,但维基百科页面说大o通常也应用于计算系统。
不,这不可能:
随着n在1/n范围内趋于无穷,我们最终得到1/(无穷),这实际上是0。
因此,问题的大-oh类将是O(0)和一个巨大的n,但更接近常数时间和一个低n。这是不明智的,因为唯一可以在比常数时间更快的时间内完成的事情是:
Void nothing() {};
甚至这也是有争议的!
只要你执行了一个命令,你至少在O(1),所以不,我们不能有一个O(1/n)的大哦类!
大o符号表示算法与典型运行时不同的最坏情况。证明O(1/n)算法是O(1)算法很简单。根据定义, O(1/n)——> T(n) <= 1/n, for all n >= C > 0 O (1 / n)——> T (n) < = 1 / C,因为1 / n <所有n > = 1 / C = C O(1/n)——> O(1),因为大O符号忽略常数(即C的值无关紧要)
没有比O(1)小的数 大o符号表示算法的最大复杂度
如果一个算法的运行时间是n³+ n²+ n + 5那么它就是O(n³) 低次在这里根本不重要,因为n ->正无穷,n^2与n^3相比是无关的
同样地,当n -> Inf时,O(1/n)与O(1)相比是不相关的,因此3 + O(1/n)将与O(1)相同,从而使O(1)的计算复杂度最小
这个问题并不像有些人认为的那样愚蠢。至少在理论上,当我们采用大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的非常简单的文本搜索算法为例。在这里,期望运行时将随着搜索模式长度的增加而减少(但是增加草堆长度将再次增加运行时)。