演算法效率

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

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

例如，冒泡排序和Timsort都是將一個列表中的每一項從小到大排序的排序算法。冒泡排序對列表進行排序的用時與元素數量平方成正比（$O(n^2)$，參見大O符號），但只需要較少量的額外記憶體，該記憶體對於列表的長度來說是常數（$O(1)$ )。Timsort對列表排序的用時與列表長度呈對數關係（$O(n\log n)$ )，但空間用量與列表長度呈線性關係 ( $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）？這有兩個方面：代碼所需的記憶體量（輔助空間使用）和代碼操作的數據所需的記憶體量（內在空間使用）。

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

- 直接功耗：直接運行電腦所需的功率。
- 間接功耗：製冷、照明等所需的電力。

從嵌入式物聯網設備到單片機再到伺服器農場，功耗正在成為所有類型和所有規模的計算任務的重要指標。這種趨勢通常被稱為綠色計算。

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

- 傳輸大小：帶寬可能是一種限制因素。數據壓縮可減少要傳輸的數據量。在網頁上顯示圖片或圖像（例如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 倍。, 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進行比較時，他指出電腦是多麼小巧而強大，但電腦編程卻多麼令人失望。

## 最佳演算法競賽

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

- 連線