有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
大o符号表示算法与典型运行时不同的最坏情况。证明O(1/n)算法是O(1)算法很简单。根据定义, O(1/n)——> T(n) <= 1/n, for all n >= C > 0 O (1 / n)——> T (n) < = 1 / C,因为1 / n <所有n > = 1 / C = C O(1/n)——> O(1),因为大O符号忽略常数(即C的值无关紧要)
其他回答
其余的大多数答案都将大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).
在数值分析中,近似算法在近似公差范围内应具有次常数的渐近复杂度。
class Function
{
public double[] ApproximateSolution(double tolerance)
{
// if this isn't sub-constant on the parameter, it's rather useless
}
}
你不能低于O(1)但是O(k) k小于N是可能的。我们称之为次线性时间算法。在某些问题中,次线性时间算法只能给出特定问题的近似解。然而,有时,一个近似解就可以了,可能是因为数据集太大了,或者计算所有数据的计算成本太高了。
随着人口增长,哪些问题会变得更容易?一个答案是像bittorrent这样的东西,下载速度是节点数量的逆函数。与汽车加载越多速度越慢相反,像bittorrent这样的文件共享网络连接的节点越多速度就越快。
有次线性算法。事实上,Bayer-Moore搜索算法就是一个很好的例子。