如何根据增长的顺序来确定哪个程序更好？

Question

一种算法运行时间的增长顺序为N;第二种算法运行时间的增长顺序为N^2。

列表两个为什么程序员宁愿使用N^2算法而不是N的令人信服的原因。

Answer 1

1. 如果实际运行时间为C0.N和C1.N²与C1.N < C0，最好使用“慢”的算法。

2. 更好的空间复杂性。

Answer 2

根据增长的顺序，您无法确定哪种算法更好。增长顺序只是根据输入数据描述所需资源的大小。所以可能会出现这样一种情况，即最复杂的程序更快，因为输入数据不够大。

例如，对排序的Java实现使用大阵列上的小阵列（即少于29个元素）和计数排序（O(N^2)）或快速排序（O(Nlog(N))）上的插入排序（O(N^2)）。

另一个例子是使用Floyd-Warshall算法（O(N^3)）代替Dijkstra算法Algortihm（O(E*logV)），因为它具有更简单的实现，并不需要一个优先级队列（因为我们没有它在任何环境实现）