演算法效率

計算機科學中，演算法效率是演算法的一種屬性，演算法效率與演算法使用的計算資源量的大小有關。分析演算法以確定其資源使用情況，即可根據不同資源的使用情況來衡量演算法的效率。演算法效率可以被認為類似於某個重複或持續過程的生產力大小。為獲得最大效率，一般希望能夠儘量減少資源使用量。然而，時間複雜度和空間複雜度等不同的資源不能直接比較，因此通常兩種演算法中哪一種各有效率取決於哪種效率計量被認為是最重要的。例如，氣泡排序和Timsort都是將一個列表中的每一項從小到大排序的排序演算法。氣泡排序對列表進行排序的用時與元素數量平方成正比，但只需要較少量的額外記憶體，該記憶體對於列表的長度來說是常數（ formula_2 )。 Timsort對列表排序的用時與列表長度呈對數關係（ formula_3 )，但空間用量與列表長度呈線性關係 ( formula_4 )。如果必須對給定應用程式的大型列表進行高速排序，則Timsort是更好的選擇；但如果以記憶體佔用最小化為重，那麼氣泡排序更優。背景.愛達·勒芙蕾絲在 1843 年強調了效率相對於時間的重要性，並將其應用於查爾斯·巴貝奇的機械分析引擎：“在幾乎每一個計算中，對於過程的連續性有各種各樣的安排是可能的，並且為了計算引擎的目的，各種考慮必須影響它們之間的選擇。一個基本目標是選擇一種能夠將完成計算所需的時間減少到最低限度的安排” 早期的電子計算機運算速度有限，隨機存取儲存器空間也有限。因此，發生了時空權衡。任務可以選擇佔用大量記憶體的快速演算法，也可以選擇使用少量記憶體的慢速演算法。而後，工程權衡來在記憶體的限制內使用最快演算法。現代計算機比早期計算機要快得多，並且可用記憶體量更大。儘管如此，Donald Knuth強調效率仍然是一個重要的考慮因素：“在已建立的工程學科中，可以輕易獲得 12% 的改進，這樣的改進從不被認為是微不足道的。我相信同樣的觀點應該在軟體工程中占主導地位。”概述.如果一個演算法的資源消耗處於或低於某個可接受的水平，則該演算法被認為是有效的。粗略地說，“可接受”意味著：它將在可用計算機上的合理時間或空間內執行，“合理時間”和“空間”通常為關於輸入資料大小的函式。自 1950 年代以來，計算機的可用計算能力和可用記憶體量都急劇增加，因此即使在 10 年前，當前可接受的水平也是不可接受的。事實上，由於摩爾定律，在現代智慧手機和嵌入式系統上可以接受的效率的任務對於 10 年前的工業伺服器來說可能效率低到無法接受。計算機制造商經常推出效能更高的新型號。由於修改軟體成本可能相當高，在某些情況下，獲得更高效能的最簡單和最便宜的方法可能是購買一臺效能更高的計算機，前提是它與現有計算機相容。有很多方法可以衡量演算法使用的資源，兩個最常見的衡量標準是速度和記憶體使用情況。其他措施可能包括傳輸速度、臨時磁碟使用、長期磁碟使用、功耗、總擁有成本、對外部刺激的響應時間等。許多這些措施取決於演算法輸入資料的大小，即要處理的資料量。它們還可能取決於資料的排列方式，例如，某些排序演算法對已經排好序或以幾乎全部按相反順序排序的資料表現不佳。在實踐中，還有其他因素會影響演算法的效率，例如對演算法準確性、可靠性的要求。如下文所述，演算法的實現方式也會對實際效率產生重大影響，儘管這在許多方面都與最佳化問題有關。理論分析.下面是應用於漸近演算法時間複雜度的大 O 符號的一些示例：基準測試：衡量效能.對於新版本的軟體或提供與競爭系統的比較，有時會使用基準測試，這有助於衡量演算法的相對效能。例如，如果產生了一種新的排序演算法，則可以將其與其前身進行比較，以確保它至少與以前一樣有效地處理已知資料，同時考慮到任何功能改進。客戶在比較替代供應商的各種產品時可以使用基準來估計哪種產品在功能和效能方面最適合他們的特定要求。例如在大型計算機領域， Syncsort等獨立軟體公司的某些專有分類產品與IBM等主要供應商的產品競爭效率。一些基準測試提供了比較分析各種編譯和解釋語言的相對速度的機會 計算機語言基準遊戲比較了幾種程式語言中典型程式設計問題的實現效能。使用各種使用者指定的標準，DIY基準測試也可以展示不同程式語言的相對效能。這很簡單，正如 "Christopher W. Cowell-Shah" 的“九種語言效能綜述”透過示例演示的那樣。演算法實現對效率的影響.演算法的實現方法也可能對效率產生影響，例如程式語言的選擇，演算法實際編寫的方式， 特定語言選擇的特定編譯器，編譯時使用的編譯選項，甚至正在使用的作業系統。在許多情況下，由直譯器實現的語言慢得多。 請關即時編譯和解釋語言的文章。還有其他因素可能會影響時間或空間效率，但這些因素可能超出程式設計師所能控制的範圍，例如資料結構對齊、資料顆粒度、訪問區域性性、快取一致性、垃圾回收、同時多縣城處理和子程式的呼叫。一些處理器具有向量處理能力，允許單指令流多資料流操作；也許程式設計師或編譯器可以輕易使用這些功能，但也有可能不可以。為順序處理設計的演算法可能需要被完全重構來利用平行計算，或者它們可以很容易地重新配置。隨著平行計算和分散式計算在 2010 年代後期變得越來越重要，並行和分散式計算系統的高效高階API被越來越多地投資。程式設計中可能出現的另一個問題是與相同指令集相容的處理器可能以不同的方式實現指令，因此在某些架構上相對較快的指令在其他架構上可能相對較慢.這通常會給最佳化編譯器帶來挑戰，編譯器必須對編譯目標平臺上可用的特定CPU和其他硬體有大量了解，才能最好地最佳化程式的效能。在極端情況下，編譯器可能被迫模擬目標平臺不支援的指令，迫使它生成程式碼或連結外部庫呼叫以產生在該目標平臺上無法計算的結果，即使它是編譯平臺上是支援的，在其他平臺上的硬體效率更高。在浮點運算的嵌入式系統中經常出現這種情況，其中微控制器通常缺乏對浮點運算的硬體支援，因此需要計算昂貴的軟體例程來產生浮點計算。資源使用量的測量.度量通常表示為輸入大小的函式formula_5 .最常見的兩種測量方法是：對於由電池供電的計算機，其他感興趣的度量是：截至2018年 (2018)[ [update]]，從嵌入式物聯網裝置到微控制器再到伺服器農場，功耗正在成為所有型別和所有規模的計算任務的重要指標。 這種趨勢通常被稱為綠色計算。在某些情況下，不太常見的計算效率度量也可能是相關的：時間.理論.分析演算法，通常使用時間複雜度分析來估計執行時間作為輸入資料大小的函式。結果通常使用大 O 表示法表示。這對於比較演算法很有用，尤其是在要處理大量資料時。當資料量較小時，需要更詳細的估計來比較演算法的效能，儘管這可能不太重要。包含並行處理的演算法可能更難分析。實踐.使用基準來計時演算法的使用。許多程式語言都有提供CPU 時間使用的可用功能。對於長時間執行的演算法，經過的時間也可能很重要。結果通常應在幾次測試中取平均值。基於執行的分析對硬體配置以及在多處理和多程式設計環境中同時執行的其他程式或任務的可能性非常敏感。這種測試還很大程度上取決於特定程式語言、編譯器和編譯器選項的選擇，因此被比較的演算法必須都在相同的條件下實現。空間.本節涉及執行演算法時記憶體資源的使用。至於上面的時間分析，分析演算法，通常使用空間複雜度分析來估計所需的執行時記憶體，作為輸入資料大小的函式。結果通常使用大 O 表示法表示。記憶體使用最多有四個方面需要考慮：早期的電子計算機和家用計算機的工作記憶體量相對較少。例如，1949 年的電子延遲儲存自動計算器的最大工作記憶體為 1024 個 17 位字，而 1980 年的 Sinclair ZX80起初具有 1024 個 8 位位元組的工作記憶體。在 2010 年代後期，個人電腦通常具有 4 到 32 GB的記憶體，這增加了 3 億多倍。快取和記憶體層次結構.當前的計算機可能具有相對較大的記憶體量，因此將演算法壓縮到有限的記憶體量中的問題比過去要小得多。但是下列四種不同型別的記憶體可能很重要：記憶體需求將適合快取記憶體記憶體的演算法將比適合主記憶體的演算法快得多，而主記憶體又將比必須求助於虛擬記憶體的演算法快得多。正因為如此，快取替換策略對於高效能計算極其重要，快取感知程式設計和資料對齊也是如此。使問題進一步複雜化的是，一些系統具有多達三個級別的快取記憶體，具有不同的有效速度。不同的系統將有不同數量的這些不同型別的記憶體，因此演算法記憶體需求的影響可能因系統而異。在電子計算的早期，如果一個演算法及其資料不適合主儲存器，那麼該演算法就無法使用。如今，虛擬記憶體的使用似乎提供了很多記憶體，但以效能為代價。如果一個演算法及其資料適合快取，那麼可以獲得非常高的速度；在這種情況下，最小化空間也有助於最小化時間。這稱為區域性性原理，可細分為參考區域性性、空間區域性性和時間區域性性。不完全適合快取記憶體但表現出引用區域性性的演算法可能會執行得相當好。對程式設計現狀的批評.“軟體效率每 18 個月減半，以補償摩爾定律。”May繼續說：“在移動平臺中，將執行的指令減半可以使電池壽命加倍，巨大的資料量將為更好的軟體和演算法帶來巨大機會：當 formula_6 很大時，將運算元從 formula_7 減少到formula_8具有顯著效果…當N=300億時，這種變化相當於 50 年的技術改進。”最佳演算法競賽.以下比賽根據由評委決定的一些任意標準邀請最佳演算法參賽：