有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
如果不管输入数据如何,答案都是一样的,那么你就有一个O(0)算法。
或者换句话说——在提交输入数据之前,答案就已经知道了 -这个功能可以优化-所以O(0)
其他回答
你不能低于O(1)但是O(k) k小于N是可能的。我们称之为次线性时间算法。在某些问题中,次线性时间算法只能给出特定问题的近似解。然而,有时,一个近似解就可以了,可能是因为数据集太大了,或者计算所有数据的计算成本太高了。
那么这个呢:
void FindRandomInList(list l)
{
while(1)
{
int rand = Random.next();
if (l.contains(rand))
return;
}
}
随着列表大小的增加,程序的预期运行时间会减少。
随着人口增长,哪些问题会变得更容易?一个答案是像bittorrent这样的东西,下载速度是节点数量的逆函数。与汽车加载越多速度越慢相反,像bittorrent这样的文件共享网络连接的节点越多速度就越快。
sharptooth是正确的,O(1)是可能的最佳性能。然而,这并不意味着一个快速的解决方案,只是一个固定时间的解决方案。
一个有趣的变种,也许是真正的建议,是随着人口的增长,哪些问题会变得更容易。我能想出一个虽然是做作的半开玩笑的答案:
一组中有两个人生日相同吗?当n超过365时,返回true。虽然小于365,这是O(nln n)。也许不是一个很好的答案,因为问题不会慢慢变得简单,而是变成O(1)对于n > 365。
这是一个简单的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.