有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
不,这不可能:
随着n在1/n范围内趋于无穷,我们最终得到1/(无穷),这实际上是0。
因此,问题的大-oh类将是O(0)和一个巨大的n,但更接近常数时间和一个低n。这是不明智的,因为唯一可以在比常数时间更快的时间内完成的事情是:
Void nothing() {};
甚至这也是有争议的!
只要你执行了一个命令,你至少在O(1),所以不,我们不能有一个O(1/n)的大哦类!
其他回答
如果解决方案存在,它可以在常数时间=立即准备和访问。例如,如果您知道排序查询是针对倒序的,则使用LIFO数据结构。然后,假设选择了适当的模型(LIFO),数据就已经排序了。
好吧,我想了一下,也许有一个算法可以遵循这个一般形式:
你需要计算一个1000节点图的旅行商问题,但是,你也有一个你不能访问的节点列表。随着不可访问节点列表的增加,问题变得更容易解决。
没有比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)的计算复杂度最小
这不可能。Big-O的定义是不大于不平等:
A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)
所以B(n)实际上是最大值,因此如果它随着n的增加而减少,估计不会改变。
这是一个简单的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.