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

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

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

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

有次线性算法。事实上，Bayer-Moore搜索算法就是一个很好的例子。

我经常用O(1/n)来描述随着输入变大而变小的概率——例如，在log2(n)次投掷中，一枚均匀硬币背面朝上的概率是O(1/n)。

那么这个呢:

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

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

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

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