算法效率
維基百科,自由的 encyclopedia
计算机科学中,算法效率是算法的一种属性,算法效率与算法使用的计算资源量的大小有关。分析算法以确定其资源使用情况,即可根据不同资源的使用情况来衡量算法的效率。算法效率可以被认为类似于某个重复或持续过程的生产力大小。
为获得最大效率,一般希望能够尽量减少资源使用量。然而,时间复杂度和空间复杂度等不同的资源不能直接比较,因此通常两种算法中哪一种各有效率取决于哪种效率计量被认为是最重要的。
例如,冒泡排序和Timsort都是将一个列表中的每一项从小到大排序的排序算法。冒泡排序对列表进行排序的用时与元素数量平方成正比( ,参见大O符号),但只需要较少量的额外内存,该内存对于列表的长度来说是常数( )。 Timsort对列表排序的用时与列表长度呈对数关系( ),但空间用量与列表长度呈线性关系 ( )。如果必须对给定应用程序的大型列表进行高速排序,则Timsort是更好的选择;但如果以内存占用最小化为重,那么冒泡排序更优。