有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于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的非常简单的文本搜索算法为例。在这里,期望运行时将随着搜索模式长度的增加而减少(但是增加草堆长度将再次增加运行时)。
其他回答
这是一个简单的O(1/n)算法。它甚至做了一些有趣的事情!
function foo(list input) {
int m;
double output;
m = (1/ input.size) * max_value;
output = 0;
for (int i = 0; i < m; i++)
output+= random(0,1);
return output;
}
O(1/n) is possible as it describes how the output of a function changes given increasing size of input. If we are using the function 1/n to describe the number of instructions a function executes then there is no requirement that the function take zero instructions for any input size. Rather, it is that for every input size, n above some threshold, the number of instructions required is bounded above by a positive constant multiplied by 1/n. As there is no actual number for which 1/n is 0, and the constant is positive, then there is no reason why the function would constrained to take 0 or fewer instructions.
你不能低于O(1)但是O(k) k小于N是可能的。我们称之为次线性时间算法。在某些问题中,次线性时间算法只能给出特定问题的近似解。然而,有时,一个近似解就可以了,可能是因为数据集太大了,或者计算所有数据的计算成本太高了。
正如已经指出的,除了null函数可能的例外,不可能有O(1/n)个函数,因为所花费的时间必须接近0。
当然,有一些算法,比如康拉德定义的算法,它们至少在某种意义上应该小于O(1)
def get_faster(list):
how_long = 1/len(list)
sleep(how_long)
If you want to investigate these algorithms, you should either define your own asymptotic measurement, or your own notion of time. For example, in the above algorithm, I could allow the use of a number of "free" operations a set amount of times. In the above algorithm, if I define t' by excluding the time for everything but the sleep, then t'=1/n, which is O(1/n). There are probably better examples, as the asymptotic behavior is trivial. In fact, I am sure that someone out there can come up with senses that give non-trivial results.
我经常用O(1/n)来描述随着输入变大而变小的概率——例如,在log2(n)次投掷中,一枚均匀硬币背面朝上的概率是O(1/n)。
如果解决方案存在,它可以在常数时间=立即准备和访问。例如,如果您知道排序查询是针对倒序的,则使用LIFO数据结构。然后,假设选择了适当的模型(LIFO),数据就已经排序了。