我正在为期末考试学习,档案中有一个问题我找不到答案:
一种算法的时间复杂度增长率为O(N^2);另一种算法的时间复杂度增长率为O(N^3)。列举三个令程序员更倾向于使用O(N^3)算法而非O(N^2)算法的充分理由。
我正在为期末考试学习,档案中有一个问题我找不到答案:
一种算法的时间复杂度增长率为O(N^2);另一种算法的时间复杂度增长率为O(N^3)。列举三个令程序员更倾向于使用O(N^3)算法而非O(N^2)算法的充分理由。
我可以想到以下三个原因:
可能第一大原因是,由于O(N2)算法的常数足够高,对于正在考虑的任务规模来说,O(N3)版本更快。
以下是一些例子,可以让你相信在某些情况下,O(N³)可能比O(N²)更好。
O(N²)算法非常复杂,而如果输入大小为N ≤ 100,则对于实际使用,O(N³)可能足够快
O(N²)的常数乘以它非常大,例如c = 1000,因此对于N = 100,c⋅N² = 1000⋅100² = 10⁷,而如果c = 1用于O(N³),那么c⋅N³ = 10⁶
O(N²)算法与O(N³)相比,具有非常高的空间复杂度
另外一件事是,一些算法有一个很大的常数因子。如果 N
足够小(如 Thorban 所指出的那样),那么一个 O(N^2)
的算法可能会有一个很大的常数因子,这将使其实际应用变得不太可行。
选择一个算法的唯一原因不是运行时间的增长顺序。您必须分析以下内容:
除了已发布的答案,我想提到缓存行为。一个特定的内存访问模式可能由于重复的缓存未命中而变得非常慢,因此在具有更友好缓存内存访问模式的理论上较慢的算法表现得更好。
大O表示最坏情况的上限。QuickSort的时间复杂度为O(n^2),而MergeSort的时间复杂度为O(n lgn)。但人们使用QuickSort是因为平均而言,其时间复杂度为O(n lgn),并且比MergeSort具有更低的常数。
100000 / 10
。现在用笔算长除法。哪个更快?在你的脑海中计算21714 / 66
。现在用笔算长除法。哪个更快?最快的方法取决于你的输入。第一个例子类似于O(n^3)
。但它对于好的数字效果很好。第二个例子类似于O(n^2)
。它通常具有更好的性能,但你不想拿出来做简单的除法。 - Mateen Ulhaq