为什么程序员更喜欢O(N^3)而不是O(N^2)？

Question

我正在为期末考试学习，档案中有一个问题我找不到答案:

一种算法的时间复杂度增长率为O(N^2)；另一种算法的时间复杂度增长率为O(N^3)。列举三个令程序员更倾向于使用O(N^3)算法而非O(N^2)算法的充分理由。

- user1922619

---

在你的脑海中计算 100000 / 10。现在用笔算长除法。哪个更快？在你的脑海中计算 21714 / 66。现在用笔算长除法。哪个更快？最快的方法取决于你的输入。第一个例子类似于 O(n^3)。但它对于好的数字效果很好。第二个例子类似于 O(n^2)。它通常具有更好的性能，但你不想拿出来做简单的除法。 - Mateen Ulhaq

Answer 1

我可以想到以下三个原因：

• 初始实现容易。
• 未来的维护容易。
• O(N^3)算法可能比O(N^2)算法具有更低的空间复杂度（即使用更少的内存）。

- Simeon Visser

---

n很小（所以并不重要） - bobobobo

@DSM 只有当常量的大小足够小，以至于被 #4 覆盖时，这才是一个好的理由。 - user395760

@delnan：对于“small”的适当含义，＃4是先决条件，但＃4并未涵盖它。不过没关系，因为现在有两个单独的答案都达到了同样的要点。 - DSM

Answer 2

可能第一大原因是，由于O(N²)算法的常数足够高，对于正在考虑的任务规模来说，O(N³)版本更快。

- Jerry Coffin

Answer 3

以下是一些例子，可以让你相信在某些情况下，O(N³)可能比O(N²)更好。

1. O(N²)算法非常复杂，而如果输入大小为N ≤ 100，则对于实际使用，O(N³)可能足够快

2. O(N²)的常数乘以它非常大，例如c = 1000，因此对于N = 100，c⋅N² = 1000⋅100² = 10⁷，而如果c = 1用于O(N³)，那么c⋅N³ = 10⁶

3. O(N²)算法与O(N³)相比，具有非常高的空间复杂度

- Vikram Bhat

---

那不是一个例子。 - djechlin

Answer 4

另外一件事是，一些算法有一个很大的常数因子。如果 N 足够小（如 Thorban 所指出的那样），那么一个 O(N^2) 的算法可能会有一个很大的常数因子，这将使其实际应用变得不太可行。

- Moha the almighty camel

---

如果输入的n足够小 - Thorben

Answer 5

选择一个算法的唯一原因不是运行时间的增长顺序。您必须分析以下内容：

• 实现起来有多容易
• 所需空间
• 现实生活中输入的大小有多大（有时时间差只在从未出现在现实中的输入大小上观察到）

- user239053

Answer 6

除了已发布的答案，我想提到缓存行为。一个特定的内存访问模式可能由于重复的缓存未命中而变得非常慢，因此在具有更友好缓存内存访问模式的理论上较慢的算法表现得更好。

- Milan

Answer 7

大O表示最坏情况的上限。QuickSort的时间复杂度为O(n^2)，而MergeSort的时间复杂度为O(n lgn)。但人们使用QuickSort是因为平均而言，其时间复杂度为O(n lgn)，并且比MergeSort具有更低的常数。

- m32rober