有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
这里有另一种方法来证明它:为了拥有一个函数,你必须调用这个函数,并且你必须返回一个答案。这需要固定的时间。即使余下的处理过程对较大的输入花费更少的时间,打印出答案(我们可以假设是单个位)至少需要常数时间。
其他回答
这是一个简单的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.
在数值分析中,近似算法在近似公差范围内应具有次常数的渐近复杂度。
class Function
{
public double[] ApproximateSolution(double tolerance)
{
// if this isn't sub-constant on the parameter, it's rather useless
}
}
我相信量子算法可以通过叠加“一次”进行多次计算……
我怀疑这是一个有用的答案。
其余的大多数答案都将大o解释为专门关于算法的运行时间。但是因为问题没有提到它,我认为值得一提的是大o在数值分析中的另一个应用,关于误差。
Many algorithms can be O(h^p) or O(n^{-p}) depending on whether you're talking about step-size (h) or number of divisions (n). For example, in Euler's method, you look for an estimate of y(h) given that you know y(0) and dy/dx (the derivative of y). Your estimate of y(h) is more accurate the closer h is to 0. So in order to find y(x) for some arbitrary x, one takes the interval 0 to x, splits it up until n pieces, and runs Euler's method at each point, to get from y(0) to y(x/n) to y(2x/n), and so on.
欧拉方法是O(h)或O(1/n)算法,其中h通常被解释为步长n被解释为你划分一个区间的次数。
在实际数值分析应用中,由于浮点舍入误差,也可以有O(1/h)。你的间隔越小,某些算法的实现就会抵消得越多,丢失的有效数字就越多,因此在算法中传播的错误也就越多。
For Euler's method, if you are using floating points, use a small enough step and cancellation and you're adding a small number to a big number, leaving the big number unchanged. For algorithms that calculate the derivative through subtracting from each other two numbers from a function evaluated at two very close positions, approximating y'(x) with (y(x+h) - y(x) / h), in smooth functions y(x+h) gets close to y(x) resulting in large cancellation and an estimate for the derivative with fewer significant figures. This will in turn propagate to whatever algorithm you require the derivative for (e.g., a boundary value problem).
O(1/n)并不小于O(1)这基本上意味着你拥有的数据越多,算法运行得越快。假设你有一个数组,如果它小于10100个元素就填充它,如果多于10100个元素就什么都不做。这个当然不是O(1/n),而是O(-n):)太糟糕了,O大符号不允许负数。