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

Question

我正在为期末考试而学习,档案中有一个问题我无法找到答案:

一种算法运行时间的增长顺序为O(N ^ 2); 第二算法的运行时间的增长顺序为O(N ^ 3).列出程序员更喜欢使用O(N ^ 3)算法而不是O(N ^ 2)算法的三个引人注目(逻辑,令人信服)的原因.

Answer 1

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

• 易于初步实施.
• 将来易于维护.
• O(N ^ 3)算法可以具有比O(N ^ 2)算法更低的空间复杂度(即,它使用更少的存储器).

Answer 2

可能是#1的原因:因为O(N ²)算法具有足够高的常数,对于正在考虑的任务的大小,O(N ³)版本更快.

Answer 3

下面举例说明O(N³)在某些情况下可能优于O(N²).

1. O(N²)算法编码非常复杂,而如果输入大小为N≤100则实际使用时O(N³)可以足够快

2. O(N²)有一个大的常数乘以它,例如c = 1000,因此N = 100,c⋅N2=1000⋅100²=10⁷而如果c = 1则O(N³)则c⋅N³=10⁶

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