有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
sharptooth是正确的,O(1)是可能的最佳性能。然而,这并不意味着一个快速的解决方案,只是一个固定时间的解决方案。
一个有趣的变种,也许是真正的建议,是随着人口的增长,哪些问题会变得更容易。我能想出一个虽然是做作的半开玩笑的答案:
一组中有两个人生日相同吗?当n超过365时,返回true。虽然小于365,这是O(nln n)。也许不是一个很好的答案,因为问题不会慢慢变得简单,而是变成O(1)对于n > 365。
其他回答
inline void O0Algorithm() {}
O(1)仅仅表示“常数时间”。
当你给循环[1]添加一个早期退出时,你(在大O符号中)把一个O(1)算法变成了O(n)算法,但使它更快。
诀窍是一般情况下,常数时间算法是最好的,线性算法比指数算法好,但对于n很小的时候,指数算法可能更快。
1:假设这个例子的列表长度是静态的
sharptooth是正确的,O(1)是可能的最佳性能。然而,这并不意味着一个快速的解决方案,只是一个固定时间的解决方案。
一个有趣的变种,也许是真正的建议,是随着人口的增长,哪些问题会变得更容易。我能想出一个虽然是做作的半开玩笑的答案:
一组中有两个人生日相同吗?当n超过365时,返回true。虽然小于365,这是O(nln n)。也许不是一个很好的答案,因为问题不会慢慢变得简单,而是变成O(1)对于n > 365。
那么这个呢:
void FindRandomInList(list l)
{
while(1)
{
int rand = Random.next();
if (l.contains(rand))
return;
}
}
随着列表大小的增加,程序的预期运行时间会减少。
不,这不可能:
随着n在1/n范围内趋于无穷,我们最终得到1/(无穷),这实际上是0。
因此,问题的大-oh类将是O(0)和一个巨大的n,但更接近常数时间和一个低n。这是不明智的,因为唯一可以在比常数时间更快的时间内完成的事情是:
Void nothing() {};
甚至这也是有争议的!
只要你执行了一个命令,你至少在O(1),所以不,我们不能有一个O(1/n)的大哦类!