算法效率

计算机科学中，算法效率是算法的一种属性，算法效率与算法使用的计算资源量的大小有关。分析算法以确定其资源使用情况，即可根据不同资源的使用情况来衡量算法的效率。算法效率可以被认为类似于某个重复或持续过程的生产力大小。

为获得最大效率，一般希望能够尽量减少资源使用量。然而，时间复杂度和空间复杂度等不同的资源不能直接比较，因此通常两种算法中哪一种各有效率取决于哪种效率计量被认为是最重要的。

例如，冒泡排序和Timsort都是将一个列表中的每一项从小到大排序的排序算法。冒泡排序对列表进行排序的用时与元素数量平方成正比（ ${\textstyle O(n^{2})}$ ，参见大O符号），但只需要较少量的额外内存，该内存对于列表的长度来说是常数（ ${\textstyle O(1)}$ )。 Timsort对列表排序的用时与列表长度呈对数关系（ ${\textstyle O(n\log n)}$ )，但空间用量与列表长度呈线性关系 ( ${\textstyle O(n)}$ )。如果必须对给定应用程序的大型列表进行高速排序，则Timsort是更好的选择；但如果以内存占用最小化为重，那么冒泡排序更优。

背景

爱达·勒芙蕾丝在 1843 年强调了效率相对于时间的重要性，并将其应用于查尔斯·巴贝奇的机械分析引擎：

“在几乎每一个计算中，对于过程的连续性有各种各样的安排是可能的，并且为了计算引擎的目的，各种考虑必须影响它们之间的选择。一个基本目标是选择一种能够将完成计算所需的时间减少到最低限度的安排” ^[1]

早期的电子计算机运算速度有限，随机存取存储器（内存）空间也有限。因此，发生了时空权衡。任务可以选择占用大量内存的快速算法，也可以选择使用少量内存的慢速算法。而后，工程权衡来在内存的限制内使用最快算法。 现代计算机比早期计算机要快得多，并且可用内存量更大（千兆字节，而不是以前的千字节）。尽管如此，Donald Knuth强调效率仍然是一个重要的考虑因素：

“在已建立的工程学科中，可以轻易获得 12% 的改进，这样的改进从不被认为是微不足道的。我相信同样的观点应该在软件工程中占主导地位。” ^[2]

概述

如果一个算法的资源消耗（也称为计算成本）处于或低于某个可接受的水平，则该算法被认为是有效的。粗略地说，“可接受”意味着：它将在可用计算机上的合理时间或空间内运行，“合理时间”和“空间”通常为关于输入数据大小的函数。自 1950 年代以来，计算机的可用计算能力和可用内存量都急剧增加，因此即使在 10 年前，当前可接受的水平也是不可接受的。事实上，由于摩尔定律，在现代智能手机和嵌入式系统上可以接受的效率的任务对于 10 年前的工业服务器来说可能效率低到无法接受。

计算机制造商经常推出性能更高的新型号。由于修改软件成本可能相当高，在某些情况下，获得更高性能的最简单和最便宜的方法可能是购买一台性能更高的计算机，前提是它与现有计算机兼容。

有很多方法可以衡量算法使用的资源，两个最常见的衡量标准是速度和内存使用情况。其他措施可能包括传输速度、临时磁盘使用、长期磁盘使用、功耗、总拥有成本、对外部刺激的响应时间等。许多这些措施取决于算法输入数据的大小，即要处理的数据量。它们还可能取决于数据的排列方式，例如，某些排序算法对已经排好序或以几乎全部按相反顺序排序的数据表现不佳。

在实践中，还有其他因素会影响算法的效率，例如对算法准确性、可靠性的要求。如下文所述，算法的实现方式也会对实际效率产生重大影响，尽管这在许多方面都与优化问题有关。

理论分析

下面是应用于渐近算法时间复杂度的大 O 符号的一些示例：

符号	名称	例子
${\displaystyle O(1)}$	常数复杂度	从排序好的列表中找到中位数；使用固定大小的查找表；使用合适的散列函数来查找一个元素。
${\displaystyle O(\log n)}$	对数复杂度	使用二叉搜索或平衡搜索树以及二项式堆中的所有操作在已排序数组中查找一个元素。
${\displaystyle O(n)}$	线性复杂度	在未排序的列表或格式错误的树（最坏的情况）或未排序的数组中查找项目；通过加法器将两个n位整数相加。
${\displaystyle O(n\log n)}$	线性复杂度、对数线性或准线性	执行快速傅里叶变换；堆排序、快速排序（最佳和平均情况）或合并排序
${\displaystyle O(n^{2})}$	平方复杂度	用简单的算法计算两个n位数的乘积；冒泡排序（最坏情况或naive implementation）、 Shell 排序、快速排序（最坏情况）、选择排序或插入排序
${\displaystyle O(c^{n}),\;c>1}$	指数复杂度	使用动态规划找到旅行商问题的最优（非近似）解；使用暴力搜索确定两个逻辑语句是否等效

基准测试：衡量性能

对于新版本的软件或提供与竞争系统的比较，有时会使用基准测试，这有助于衡量算法的相对性能。例如，如果产生了一种新的排序算法，则可以将其与其前身进行比较，以确保它至少与以前一样有效地处理已知数据，同时考虑到任何功能改进。客户在比较替代供应商的各种产品时可以使用基准来估计哪种产品在功能和性能方面最适合他们的特定要求。例如在大型计算机领域， Syncsort等独立软件公司的某些专有分类产品与IBM等主要供应商的产品竞争效率。

一些基准测试提供了比较分析各种编译和解释语言的相对速度的机会^{[3] [4]}计算机语言基准游戏比较了几种编程语言中典型编程问题的实现性能。

使用各种用户指定的标准，DIY基准测试也可以展示不同编程语言的相对性能。这很简单，正如 Christopher W. Cowell-Shah 的“九种语言性能综述”通过示例演示的那样。 ^[5]

算法实现对效率的影响

算法的实现方法也可能对效率产生影响，例如编程语言的选择，算法实际编写的方式， ^[6]特定语言选择的特定编译器，编译时使用的编译选项，甚至正在使用的操作系统。在许多情况下，由解释器实现的语言（解释语言）可能比由编译器实现的语言（编译语言）慢得多。 ^[3]请参阅有关即时编译和解释语言的文章。

还有其他因素可能会影响时间或空间效率，但这些因素可能超出程序员所能控制的范围，例如数据结构对齐、数据颗粒度、访问局部性、快取一致性、垃圾回收（GC）、指令层级并行、多线程（硬件或软件级别）、同时多县城处理和子程序的调用。 ^[7]

一些处理器具有向量处理能力，允许单指令流多数据流操作；也许程序员或编译器可以轻易使用这些功能，但也有可能不可以。为顺序处理设计的算法可能需要被完全重构来利用并行计算，或者它们可以很容易地重新配置。随着并行计算和分布式计算在 2010 年代后期变得越来越重要，并行和分布式计算系统（如CUDA 、 TensorFlow 、 Hadoop 、 OpenMP和MPI ）的高效高级API被越来越多地投资。

编程中可能出现的另一个问题是与相同指令集（例如x86-64或ARM ）兼容的处理器可能以不同的方式实现指令，因此在某些架构上相对较快的指令在其他架构上可能相对较慢.这通常会给优化编译器带来挑战，编译器必须对编译目标平台上可用的特定CPU和其他硬件有大量了解，才能最好地优化程序的性能。在极端情况下，编译器可能被迫模拟目标平台不支持的指令，迫使它生成代码或链接外部库调用以产生在该目标平台上无法计算的结果，即使它是编译平台上是支持的，在其他平台上的硬件效率更高。在浮点运算的嵌入式系统中经常出现这种情况，其中单片机通常缺乏对浮点运算的硬件支持，因此需要计算昂贵的软件例程来产生浮点计算。

资源使用量的测量

度量通常表示为输入大小的函数${\displaystyle \scriptstyle {n}}$  .

最常见的两种测量方法是：

• 时间：算法完成需要多长时间？
• 空间：算法需要多少工作内存（通常是 RAM）？这有两个方面：代码所需的内存量（辅助空间使用）和代码操作的数据所需的内存量（内在空间使用）。

对于由电池供电的计算机（例如笔记本电脑和智能手机），或用于非常长时间或大量计算的计算机（例如超级计算机），其他感兴趣的度量是：

• 直接功耗：直接运行计算机所需的功率。
• 间接功耗：制冷、照明等所需的电力。

截至2018年 (2018-Missing required parameter 1=month!)^[update]，从嵌入式物联网设备到单片机再到服务器农场，功耗正在成为所有类型和所有规模的计算任务的重要指标。 这种趋势通常被称为绿色计算。

在某些情况下，不太常见的计算效率度量也可能是相关的：

• 传输大小：带宽可能是一种限制因素。数据压缩可减少要传输的数据量。在网页上显示图片或图像（例如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 倍）。 ^[8]若L1缓存未命中并且必须从L2缓存中检索和写入，则速度会慢 10 倍；如果 L2 缓存仍未命中并且必须从L3缓存中检索，则会再慢 10 倍。
• 主内存通常以动态RAM (DRAM) 实现。主内存比 L3 CPU 缓存大得多（通常为千兆字节，而 ≈8兆字节），读取和写入延迟通常慢 10-100 倍。 ^[8]截至2018年 (2018-Missing required parameter 1=month!)^[update] , RAM 越来越多地在处理器的芯片上实现，如 CPU 或GPU 内存。
• 虚拟内存一般在二级存储（如硬盘）中实现，它是内存层次结构的扩展，更大的存储空间更大但延迟更大，通常比 RAM 中缓存未命中慢约 1000 倍。^[8]虽然最初的动机是创造比实际可用内存更多的印象，但虚拟内存在当代使用中更为重要，因为它的时空权衡和支持虚拟机的使用。 ^[8]在虚拟内存中，来自主内存的高速缓存未命中称为页面错误，将对程序造成巨大的性能损失。

内存需求将适合高速缓存内存的算法将比适合主内存的算法快得多，而主内存又将比必须求助于虚拟内存的算法快得多。正因为如此，缓存替换策略对于高性能计算极其重要，缓存感知编程和数据对齐也是如此。使问题进一步复杂化的是，一些系统具有多达三个级别的高速缓存，具有不同的有效速度。不同的系统将有不同数量的这些不同类型的内存，因此算法内存需求的影响可能因系统而异。

在电子计算的早期，如果一个算法及其数据不适合主存储器，那么该算法就无法使用。如今，虚拟内存的使用似乎提供了很多内存，但以性能为代价。如果一个算法及其数据适合缓存，那么可以获得非常高的速度；在这种情况下，最小化空间也有助于最小化时间。这称为局部性原理，可细分为参考局部性、空间局部性和时间局部性。不完全适合高速缓存但表现出引用局部性的算法可能会执行得相当好。

对编程现状的批评

• 英国计算机科学家、现任布里斯托大学计算机科学教授、 XMOS Semiconductor创始人兼首席技术官David May FRS 认为，问题之一是依赖摩尔定律来解决低效率问题。他提出了摩尔定律（梅定律）的“替代方案”，如下所述： ^[9]

“软件效率每 18 个月减半，以补偿摩尔定律。”

May继续说：

“在移动平台中，将执行的指令减半可以使电池寿命加倍，巨大的数据量将为更好的软件和算法带来巨大机会：当 ${\displaystyle N}$  很大时，将操作数从 ${\displaystyle N^{2}}$  减少到${\displaystyle N\log {N}}$ 具有显著效果…当N=300亿时，这种变化相当于 50 年的技术改进。”

• 软件作者 Adam N. Rosenburg 在他的博客“数字计算机的失败”中将当前的编程状态描述为接近“软件事件视界”，（暗指道格拉斯亚当斯的《银河系漫游指南》^[10] ）。他估计自 1980 年代以来，已经有70dB的生产力因子损失或“其交付货物能力的 99.99999%” ——当Arthur C. Clarke在他的著作2001: A Space Odyssey中将 2001 年的计算现实与计算机HAL 9000进行比较时，他指出计算机是多么小巧而强大，但计算机编程却多么令人失望。

最佳算法竞赛

以下比赛根据由评委决定的一些任意标准邀请最佳算法参赛：

• 连线^[11]

参见

• 算法分析
• 算术编码
• 关联数组
• 基准测试
• 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

参考

1. Green, Christopher, Classics in the History of Psychology, [19 May 2013], （原始内容于2013-09-27） 
2. Knuth, Donald, (PDF), Computing Surveys, 1974, 6 (4): 261–301 [19 May 2013], Bibcode:10.1.1.103.6084 请检查|bibcode=值 (帮助), doi:10.1145/356635.356640, （原始内容 (PDF)存档于24 August 2009） 
3. Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason). Fourmilab.ch. 4 August 2005 [14 December 2011]. （原始内容于2011-12-11）. 
4. Whetstone Benchmark History. Roylongbottom.org.uk. [14 December 2011]. （原始内容于2012-01-15）. 
5. OSNews Staff. Nine Language Performance Round-up: Benchmarking Math & File I/O. www.osnews.com. [2018-09-18]. （原始内容于2019-11-28）. 
6. Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur. The (black) art of runtime evaluation: Are we comparing algorithms or implementations?. Knowledge and Information Systems. 2016, 52 (2): 341–378. ISSN 0219-1377. doi:10.1007/s10115-016-1004-2. 
7. Guy Lewis Steele, Jr. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.
8. Hennessy, John L; Patterson, David A; Asanović, Krste; Bakos, Jason D; Colwell, Robert P; Bhattacharjee, Abhishek; Conte, Thomas M; Duato, José; Franklin, Diana. Computer Architecture: a Quantitative Approach Sixth. 2011. ISBN 978-0128119051. OCLC 983459758 （英语）. 
9. (PDF). [23 February 2009]. （原始内容 (PDF)存档于3 March 2016）. 
10. The Failure of the Digital Computer. [2022-05-04]. （原始内容于2019-11-23）. 
11. Fagone, Jason. Teen Mathletes Do Battle at Algorithm Olympics. Wired. 29 November 2010 [2022-05-04]. （原始内容于2014-03-16）.