算法效率

計算機科學中，算法效率是算法的一種屬性，算法效率與算法使用的計算資源量的大小有關。分析算法以確定其資源使用情況，即可根據不同資源的使用情況來衡量算法的效率。算法效率可以被認為類似於某個重複或持續過程的生產力大小。

為獲得最大效率，一般希望能夠儘量減少資源使用量。然而，時間複雜度和空間複雜度等不同的資源不能直接比較，因此通常兩種算法中哪一種各有效率取決於哪種效率計量被認為是最重要的。

例如，冒泡排序和Timsort都是將一個列表中的每一項從小到大排序的排序算法。冒泡排序對列表進行排序的用時與元素數量平方成正比（ ${\textstyle O(n^{2})}$ ，參見大O符號），但只需要較少量的額外內存，該內存對於列表的長度來說是常數（ ${\textstyle O(1)}$ )。 Timsort對列表排序的用時與列表長度呈對數關係（ ${\textstyle O(n\log n)}$ )，但空間用量與列表長度呈線性關係 ( ${\textstyle O(n)}$ )。如果必須對給定應用程式的大型列表進行高速排序，則Timsort是更好的選擇；但如果以內存佔用最小化為重，那麼冒泡排序更優。

背景

愛達·勒芙蕾絲在 1843 年強調了效率相對於時間的重要性，並將其應用於查爾斯·巴貝奇的機械分析引擎：

「在幾乎每一個計算中，對於過程的連續性有各種各樣的安排是可能的，並且為了計算引擎的目的，各種考慮必須影響它們之間的選擇。一個基本目標是選擇一種能夠將完成計算所需的時間減少到最低限度的安排」

早期的電子計算機運算速度有限，隨機存取存儲器（內存）空間也有限。因此，發生了時空權衡。任務可以選擇佔用大量內存的快速算法，也可以選擇使用少量內存的慢速算法。而後，工程權衡來在內存的限制內使用最快算法。 現代計算機比早期計算機要快得多，並且可用內存量更大（千兆字節，而不是以前的千字節）。儘管如此，Donald Knuth強調效率仍然是一個重要的考慮因素：

「在已建立的工程學科中，可以輕易獲得 12% 的改進，這樣的改進從不被認為是微不足道的。我相信同樣的觀點應該在軟件工程中佔主導地位。」

概述

如果一個算法的資源消耗（也稱為計算成本）處於或低於某個可接受的水平，則該算法被認為是有效的。粗略地說，「可接受」意味着：它將在可用計算機上的合理時間或空間內運行，「合理時間」和「空間」通常為關於輸入數據大小的函數。自 1950 年代以來，計算機的可用計算能力和可用內存量都急劇增加，因此即使在 10 年前，當前可接受的水平也是不可接受的。事實上，由於摩爾定律，在現代智能手機和嵌入式系統上可以接受的效率的任務對於 10 年前的工業伺服器來說可能效率低到無法接受。

計算機製造商經常推出性能更高的新型號。由於修改軟件成本可能相當高，在某些情況下，獲得更高性能的最簡單和最便宜的方法可能是購買一台性能更高的計算機，前提是它與現有計算機兼容。

有很多方法可以衡量算法使用的資源，兩個最常見的衡量標準是速度和內存使用情況。其他措施可能包括傳輸速度、臨時磁盤使用、長期磁盤使用、功耗、總擁有成本、對外部刺激的響應時間等。許多這些措施取決於算法輸入數據的大小，即要處理的數據量。它們還可能取決於數據的排列方式，例如，某些排序算法對已經排好序或以幾乎全部按相反順序排序的數據表現不佳。

在實踐中，還有其他因素會影響算法的效率，例如對算法準確性、可靠性的要求。如下文所述，算法的實現方式也會對實際效率產生重大影響，儘管這在許多方面都與優化問題有關。

理論分析

下面是應用於漸近算法時間複雜度的大 O 符號的一些示例：

符號	名稱	例子
$O(1)$	常數複雜度	從排序好的列表中找到中位數；使用固定大小的查找表；使用合適的散列函數來查找一個元素。
$O(\log n)$	對數複雜度	使用二叉搜索或平衡搜索樹以及二項式堆中的所有操作在已排序數組中查找一個元素。
$O(n)$	線性複雜度	在未排序的列表或格式錯誤的樹（最壞的情況）或未排序的數組中查找項目；通過加法器將兩個n位整數相加。
$O(n\log n)$	線性複雜度、對數線性或準線性	執行快速傅里葉變換；堆排序、快速排序（最佳和平均情況）或合併排序
$O(n^{2})$	平方複雜度	用簡單的算法計算兩個n位數的乘積；冒泡排序（最壞情況或naive implementation）、 Shell 排序、快速排序（最壞情況）、選擇排序或插入排序
$O(c^{n}),\;c>1$	指數複雜度	使用動態規劃找到旅行商問題的最優（非近似）解；使用暴力搜索確定兩個邏輯語句是否等效

基準測試：衡量性能

對於新版本的軟件或提供與競爭系統的比較，有時會使用基準測試，這有助于衡量算法的相對性能。例如，如果產生了一種新的排序算法，則可以將其與其前身進行比較，以確保它至少與以前一樣有效地處理已知數據，同時考慮到任何功能改進。客戶在比較替代供應商的各種產品時可以使用基準來估計哪種產品在功能和性能方面最適合他們的特定要求。例如在大型計算機領域， Syncsort等獨立軟件公司的某些專有分類產品與IBM等主要供應商的產品競爭效率。

一些基準測試提供了比較分析各種編譯和解釋語言的相對速度的機會 計算機語言基準遊戲比較了幾種程式語言中典型編程問題的實現性能。

使用各種用戶指定的標準，DIY基準測試也可以展示不同程式語言的相對性能。這很簡單，正如 Christopher W. Cowell-Shah 的「九種語言性能綜述」通過示例演示的那樣。

算法實現對效率的影響

算法的實現方法也可能對效率產生影響，例如程式語言的選擇，算法實際編寫的方式， 特定語言選擇的特定編譯器，編譯時使用的編譯選項，甚至正在使用的作業系統。在許多情況下，由解釋器實現的語言（解釋語言）可能比由編譯器實現的語言（編譯語言）慢得多。 請參閱有關即時編譯和解釋語言的文章。

還有其他因素可能會影響時間或空間效率，但這些因素可能超出程式設計師所能控制的範圍，例如數據結構對齊、數據顆粒度、訪問局部性、快取一致性、垃圾回收（GC）、指令層級並行、多線程（硬件或軟件級別）、同時多縣城處理和子程序的調用。

一些處理器具有向量處理能力，允許單指令流多數據流操作；也許程式設計師或編譯器可以輕易使用這些功能，但也有可能不可以。為順序處理設計的算法可能需要被完全重構來利用並行計算，或者它們可以很容易地重新配置。隨着並行計算和分佈式計算在 2010 年代後期變得越來越重要，並行和分佈式計算系統（如CUDA 、 TensorFlow 、 Hadoop 、 OpenMP和MPI ）的高效高級API被越來越多地投資。

編程中可能出現的另一個問題是與相同指令集（例如x86-64或ARM ）兼容的處理器可能以不同的方式實現指令，因此在某些架構上相對較快的指令在其他架構上可能相對較慢.這通常會給優化編譯器帶來挑戰，編譯器必須對編譯目標平台上可用的特定CPU和其他硬件有大量了解，才能最好地優化程序的性能。在極端情況下，編譯器可能被迫模擬目標平台不支持的指令，迫使它生成代碼或連結外部庫調用以產生在該目標平台上無法計算的結果，即使它是編譯平台上是支持的，在其他平台上的硬件效率更高。在浮點運算的嵌入式系統中經常出現這種情況，其中單片機通常缺乏對浮點運算的硬件支持，因此需要計算昂貴的軟件例程來產生浮點計算。

資源使用量的測量

度量通常表示為輸入大小的函數$\scriptstyle {n}$ .

最常見的兩種測量方法是：

• 時間：算法完成需要多長時間？
• 空間：算法需要多少工作內存（通常是 RAM）？這有兩個方面：代碼所需的內存量（輔助空間使用）和代碼操作的數據所需的內存量（內在空間使用）。

對於由電池供電的計算機（例如筆記本電腦和智能手機），或用於非常長時間或大量計算的計算機（例如超級計算機），其他感興趣的度量是：

• 直接功耗：直接運行計算機所需的功率。
• 間接功耗：製冷、照明等所需的電力。

截至2018年 (2018-Missing required parameter 1=month!)，從嵌入式物聯網設備到單片機再到伺服器農場，功耗正在成為所有類型和所有規模的計算任務的重要指標。 這種趨勢通常被稱為綠色計算。

在某些情況下，不太常見的計算效率度量也可能是相關的：

• 傳輸大小：帶寬可能是一種限制因素。數據壓縮可減少要傳輸的數據量。在網頁上顯示圖片或圖像（例如Google logo）可能會導致傳輸數萬字節的數據（在本例中為 48K），而若只傳輸文本「Google」則為 6 個字節。這對於I/O 綁定的計算任務而言很重要。
• 外部空間：運行算法在磁盤或其他外部存儲設備所需的空間。這可能是算法執行時的臨時存儲，也可能是需要進行長期存儲以備將來使用。
• 響應時間（延遲）：當計算機系統必須快速響應某些外部事件時，這與實時計算特別相關。
• 總擁有成本：如果計算機專用於一種特定算法，這將特別受關注。

時間

理論

分析算法，通常使用時間複雜度分析來估計運行時間作為輸入數據大小的函數。結果通常使用大 O 表示法表示。這對於比較算法很有用，尤其是在要處理大量數據時。當數據量較小時，需要更詳細的估計來比較算法的性能，儘管這可能不太重要。包含並行處理的算法可能更難分析。

實踐

使用基準來計時算法的使用。許多程式語言都有提供CPU 時間使用的可用功能。對於長時間運行的算法，經過的時間也可能很重要。結果通常應在幾次測試中取平均值。

基於運行的分析對硬件配置以及在多處理和多編程環境中同時運行的其他程序或任務的可能性非常敏感。

這種測試還很大程度上取決於特定程式語言、編譯器和編譯器選項的選擇，因此被比較的算法必須都在相同的條件下實現。

空間

本節涉及執行算法時內存資源（寄存器、緩存、 RAM 、虛擬內存、輔助內存）的使用。至於上面的時間分析，分析算法，通常使用空間複雜度分析來估計所需的運行時內存，作為輸入數據大小的函數。結果通常使用大 O 表示法表示。

內存使用最多有四個方面需要考慮：

• 保存算法代碼所需的內存量。
• 輸入數據所需的內存量。
• 任何輸出數據所需的內存量。
  • 一些算法，例如排序，通常會重新排列輸入數據，並且不需要任何額外的空間來存儲輸出數據。此屬性稱為「就地」操作。
• 計算期間作為工作空間所需的內存量。
  • 這包括局部變量和計算期間調用的例程所需的任何堆疊空間；這個堆疊空間對於使用遞歸技術的算法可能很重要。

早期的電子計算機和家用計算機的工作內存量相對較少。例如，1949 年的電子延遲存儲自動計算器（EDSAC）的最大工作內存為 1024 個 17 位字，而 1980 年的 Sinclair ZX80起初具有 1024 個 8 位字節的工作內存。在 2010 年代後期，個人電腦通常具有 4 到 32 GB的內存，這增加了 3 億多倍。

緩存和內存層次結構

當前的計算機可能具有相對較大的內存量（可能是千兆字節），因此將算法壓縮到有限的內存量中的問題比過去要小得多。但是下列四種不同類型的內存可能很重要：

• 寄存器，最快的計算機內存，但存儲空間最少。現代計算機上的大多數直接計算發生在寄存器中的源操作數和目標操作數，然後根據需要更新到緩存、主內存和虛擬內存。在處理器內核上，通常有數百字節或更少的可用寄存器，儘管寄存器堆可能包含的物理架構寄存器可能比指令集架構中定義的更多。
• 高速緩衝是計算機第二快和第二小的可用內存。緩存位於 CPU、GPU、硬盤驅動器和外圍設備中，通常以靜態RAM的方式實現。內存緩存分為多個層級；較低的級別更大、更慢，並且通常在多核處理器中的處理器內核之間共享。為了處理高速緩存中的操作數，處理單元必須從高速緩存中取出數據，在寄存器中執行操作並將數據寫回高速緩存。在L1 緩存中，它的運行速度與 CPU 或 GPU 的算術邏輯單元或浮點單元相當（大約慢 2-10 倍）。 若L1緩存未命中並且必須從L2緩存中檢索和寫入，則速度會慢 10 倍；如果 L2 緩存仍未命中並且必須從L3緩存中檢索，則會再慢 10 倍。
• 主內存通常以動態RAM (DRAM) 實現。主內存比 L3 CPU 緩存大得多（通常為千兆字節，而 ≈8兆字節），讀取和寫入延遲通常慢 10-100 倍。 截至2018年 (2018-Missing required parameter 1=month!) , RAM 越來越多地在處理器的晶片上實現，如 CPU 或GPU 內存。
• 虛擬內存一般在二級存儲（如硬盤）中實現，它是內存層次結構的擴展，更大的存儲空間更大但延遲更大，通常比 RAM 中緩存未命中慢約 1000 倍。雖然最初的動機是創造比實際可用內存更多的印象，但虛擬內存在當代使用中更為重要，因為它的時空權衡和支持虛擬機的使用。 在虛擬內存中，來自主內存的高速緩存未命中稱為頁面錯誤，將對程序造成巨大的性能損失。

內存需求將適合高速緩存內存的算法將比適合主內存的算法快得多，而主內存又將比必須求助於虛擬內存的算法快得多。正因為如此，緩存替換策略對於高性能計算極其重要，緩存感知編程和數據對齊也是如此。使問題進一步複雜化的是，一些系統具有多達三個級別的高速緩存，具有不同的有效速度。不同的系統將有不同數量的這些不同類型的內存，因此算法內存需求的影響可能因系統而異。

在電子計算的早期，如果一個算法及其數據不適合主存儲器，那麼該算法就無法使用。如今，虛擬內存的使用似乎提供了很多內存，但以性能為代價。如果一個算法及其數據適合緩存，那麼可以獲得非常高的速度；在這種情況下，最小化空間也有助於最小化時間。這稱為局部性原理，可細分為參考局部性、空間局部性和時間局部性。不完全適合高速緩存但表現出引用局部性的算法可能會執行得相當好。

對編程現狀的批評

• 英國計算機科學家、現任布里斯托大學計算機科學教授、 XMOS Semiconductor創始人兼首席技術官David May FRS 認為，問題之一是依賴摩爾定律來解決低效率問題。他提出了摩爾定律（梅定律）的「替代方案」，如下所述：

「軟件效率每 18 個月減半，以補償摩爾定律。」

May繼續說：

「在移動平台中，將執行的指令減半可以使電池壽命加倍，巨大的數據量將為更好的軟件和算法帶來巨大機會：當 $N$ 很大時，將操作數從 $N^{2}$ 減少到$N\log {N}$具有顯著效果…當N=300億時，這種變化相當於 50 年的技術改進。」

• 軟件作者 Adam N. Rosenburg 在他的博客「數字計算機的失敗」中將當前的編程狀態描述為接近「軟件事件視界」，（暗指道格拉斯亞當斯的《銀河系漫遊指南》 ）。他估計自 1980 年代以來，已經有70dB的生產力因子損失或「其交付貨物能力的 99.99999%」 ——當Arthur C. Clarke在他的著作2001: A Space Odyssey中將 2001 年的計算現實與計算機HAL 9000進行比較時，他指出計算機是多麼小巧而強大，但計算機編程卻多麼令人失望。

最佳算法競賽

以下比賽根據由評委決定的一些任意標準邀請最佳算法參賽：

• 連線

參見

• 算法分析
• 算術編碼
• 關聯數組
• 基準測試
• Best, worst and average case
• 二分搜尋演算法
• Branch table
• Comparison of programming paradigms
• Compiler optimization
• Computational complexity of mathematical operations
• 計算複雜性理論
• 電腦性能
• 數據壓縮
• 數據庫索引
• 熵編碼法
• 垃圾回收 (計算機科學)
• 綠色計算
• 霍夫曼編碼
• 訪問局部性
• Loop optimization
• 記憶體管理
• Optimization (computer science)
• 性能分析
• 實時計算
• 算法分析
• 同時多線程
• Sorting algorithm § Comparison of algorithms
• 推測執行
• 求值策略
• 分支預測器
• Super-threading
  • 超執行緒
• Threaded code
• Virtual method table