O(N*N)的时间复杂度能比O(N)更快吗？

Question

有没有人能给我一个现实的例子，其中一个 O(N*N) 算法比一个 O(N) 算法对于一些 N>10 更快。

编辑：我看到这个问题因为太泛化而被搁置了。但我的问题确实是泛化的。没有其他的方式可以用不同的方式提出这个问题。

- anurag86

---

这是一项课堂作业吗？ - Topological Sort

不是 O(n^2) 和 O(N) 的问题，而是当数据的大小较小时，冒泡排序比快速排序更快，因为快速排序的开销超过了冒泡排序的速度。 - NathanOliver

答案不在后面吗？如果你只是在这里问，做练习有什么帮助呢？ - Useless

当元素数量较少但范围较大时（因为需要遍历直方图中的所有条目），可以使用计数排序（Counting-Sort）。例如，考虑元素 4,8,6,2,999999 的计数排序。您需要扫描一个百万条目的数组才能完成这种类型的排序，但您可以在大约 5*5 次迭代中执行任何“标准”排序。 - barak manos

另一个 Stroustrup 的亮点是 O(1) 列表操作，而不是 O(N) 向量操作，其中列表速度远慢于向量（由于缓存）。 - Ryan Haining

Answer 1

可能有些人试图将一个O(N*N)的算法变得更快（例如通过引入一些数据预处理），最终得到了像这样的东西：

O(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

- 463035818_is_not_a_number

---

大O符号只是针对大N的极限行为。常数（或线性）部分可能会有很大差异。 - David Titarenco

@DavidTitarenco 更好了吗？ - 463035818_is_not_a_number

为什么会有没有评论的踩？如果我知道哪里出了问题，我会进行修复，但是由于我不知道该如何修复，所以我可能会直接删除它... - 463035818_is_not_a_number

@Peter Cordes：所以底线是，常数可能使O(NN)比O(N)更好。大O表示最坏情况，它并不意味着O(NN)总是O(N*N)。例如，我试图在一个包含一百万个元素的数组中查找一个数字。最坏情况是要查找的数字在末尾。但是这个数字仍然可能在开头。这是所有答案的要点吗？我的理解正确吗？ - anurag86

无论如何，仅通过它们的大O时间复杂度比较两个算法只能告诉您哪个在N趋近于无穷时最好，没有更多的保证。通常，在合理的规模下，具有更好复杂度的算法获胜，但是有些理论上更好的算法在实际硬件上表现不佳，并且在使用过大的问题规模时也不会更快，因此毫无意义。 - Peter Cordes

Answer 2

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

大O符号仅描述算法的渐近性能，当N趋向于正无穷时。

最重要的是：它描述算法的理论性能 - 而不是其实际实现的性能！

这就是为什么常数和与其他开销相关的小函数被省略在大O符号之外。当N趋近于无穷大时，它们对主要函数的形状没有影响（尤其是）- 但它们对分析算法实现的实际性能至关重要。

简单的例子。在qsort()函数中放置sleep(60)。渐近地，该算法仍然是相同的O(N*log(N))算法，因为60秒的常数睡眠与无限相比微不足道。但在实际情况下，这样的qsort()实现将被任何冒泡排序实现（当然没有sleep()）超越，因为现在N*log(N)前面是巨大的常数。

- Dummy00001

Answer 3

输入一个整数n。

第一个例子：一对利用O符号是一个上界的短程序，因此一个O(1)程序也是O(n)和O(n^2)等等...

程序1：

def prog1(n)
    1.upto(n) do |i|
    end
end

程序2：

def prog2(n)
    return
end

程序1是O(n)，程序2是O(n*n)，以及O(n)、O(1)和O(n^n^n^n^n)。

然而，程序2比程序1更快。

第二个例子：一对利用O符号依赖于n的行为的程序。

程序1：与之前相同

程序2：

def prog2(n)
    if n < 10^100
        return
    else
        1.upto(n) do |i|
            1.upto(n) do |j|
            end
        end
    end
end

程序1的时间复杂度为O(n)，而程序2的时间复杂度为O(n*n)。

然而，当n >= 10^100时，程序2比程序1更快。

- Dave

---

我不明白你的第二个程序怎么是O(n*n)的。它与你得到的参数无关。 - anurag86

因为O(n)中的所有内容都在O(n^2)中，而O(1)中的所有内容都在O(n)中。 - Chad S.

@anurag86 O表示法给出了一个上界。Theta表示法给出了一个紧密的界限。Omega表示法给出了一个下界。如果某物是O（f（n）），那么对于所有g> = f（即 g（n）/f（n）的极限n->无穷大> = 1），它也是O（g（n））。 - Dave

这是一个正确但无用的答案。显然，OP认为O(n^2)是O(n^2)算法运行时间的紧密上界。如果你想挑剔使用大O而不是大Omega，你应该直接说出来。不需要示例代码。 - Peter Cordes

@PeterCordes 我不同意。对于一些搞不清 big-O 意义的人，而这样的人很多，如果他们看到一个具体的例子，那么他们更可能学会它是一个上限，尽管我应该在我的答案中说明这一点，而不是在评论中提出。 - Dave

Answer 4

作为一个现实的例子，可以看看我的回答和这个问题。

中位数可以在O(N)时间内找到（无论是在最坏情况下还是平均情况下）。例如，这样的算法在std::nth_element中实现。

然而，对于小的N，一个具有O(N^2)复杂度的算法可能会更快，因为1）它没有分支，2）它可以使用SSE进行向量化。至少对于short类型的N=23元素，它比std::nth_element快4-5倍。这种特定的设置在图像处理中有应用。

P.S. 顺便说一句，当N <= 32时，std::nth_element的实现通常在内部使用插入排序，这也是一个O(N^2)算法。

- stgatilov