算法效率
維基百科,自由的 encyclopedia
計算機科學中,算法效率是算法的一種屬性,算法效率與算法使用的計算資源量的大小有關。分析算法以確定其資源使用情況,即可根據不同資源的使用情況來衡量算法的效率。算法效率可以被認為類似於某個重複或持續過程的生產力大小。
為獲得最大效率,一般希望能夠儘量減少資源使用量。然而,時間複雜度和空間複雜度等不同的資源不能直接比較,因此通常兩種算法中哪一種各有效率取決於哪種效率計量被認為是最重要的。
例如,冒泡排序和Timsort都是將一個列表中的每一項從小到大排序的排序算法。冒泡排序對列表進行排序的用時與元素數量平方成正比( ,參見大O符號),但只需要較少量的額外內存,該內存對於列表的長度來說是常數(
)。 Timsort對列表排序的用時與列表長度呈對數關係(
),但空間用量與列表長度呈線性關係 (
)。如果必須對給定應用程式的大型列表進行高速排序,則Timsort是更好的選擇;但如果以內存佔用最小化為重,那麼冒泡排序更優。