O(N*N)能否比O(N)快

Question

有人能给我一个现实的例子,其中O(N*N)算法比O(N)某些算法更快N>10.

编辑:我认为这个问题因过于笼统而被搁置.但我确实只有一般性问题.没有其他方式可以以不同的方式提出这个问题.

Answer 1

可能有些人试图使 O(N*N) 算法更快（例如，通过引入一些数据预处理）并最终得到如下结果：

在）：

for (int i=0;i<N;i++){
    // do some expensive preconditioning of your data
    // to enable using O(N) algorithm
}
for (int i=0;i<N;i++){
    // run the actual O(N) algorithm
}

O(N*N)：

for (int i=0;i<N;i++){
    for (int j=0;j<N;j++){
        // run the O(N*N) algorithm
    }
}

大 O 表示法只是大 N 的限制行为。常数（或线性）部分可能有很大差异。例如，可能是这样的

O(N)   =           N + 10000 
O(N*N) = N^2 + 0.5*N +    10