有没有O(1/n)种算法?

或者其他小于O(1)的数?


当前回答

是的。

只有一种算法运行时为O(1/n),即“空”算法。

对于O(1/n)的算法来说,这意味着它渐进地执行的步骤比由单个指令组成的算法少。如果对于所有n个> n0,它执行的步骤少于1步,则对于这n个,它必须完全不包含任何指令。由于检查' If n > n0'至少需要1条指令,因此对于所有n个,它必须不包含任何指令。

总结: 唯一的算法是O(1/n)是空算法,不包含任何指令。

其他回答

在数值分析中,近似算法在近似公差范围内应具有次常数的渐近复杂度。

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}

如果不管输入数据如何,答案都是一样的,那么你就有一个O(0)算法。

或者换句话说——在提交输入数据之前,答案就已经知道了 -这个功能可以优化-所以O(0)

我相信量子算法可以通过叠加“一次”进行多次计算……

我怀疑这是一个有用的答案。

如果解决方案存在,它可以在常数时间=立即准备和访问。例如,如果您知道排序查询是针对倒序的,则使用LIFO数据结构。然后,假设选择了适当的模型(LIFO),数据就已经排序了。

那么这个呢:

void FindRandomInList(list l)
{
    while(1)
    {
        int rand = Random.next();
        if (l.contains(rand))
            return;
    }
}

随着列表大小的增加,程序的预期运行时间会减少。