渐近分析

渐近分析描述了算法的运行时间或内存如何随着输入规模的增大而增长，使用大O、大Omega和大Theta等符号来捕捉增长率，同时忽略常数和低阶项。

Definition

渐近分析是对函数在其自变量趋于无穷大时的增长率的表征；在算法分析中，它表示时间或空间使用量如何随输入规模扩展，使用阶数记法来抑制常数因子和低阶项。

Scope

本主题涵盖了用于表征资源使用的渐近符号——大O（上界）、大Omega（下界）、大Theta（紧密界），以及严格的小o和小omega——以及标准增长类别（常数、对数、线性、线性对数、多项式、指数）和操纵这些边界的规则。它解释了为什么常数因子和低阶项被抽象掉，以及渐近比较如何预测扩展行为。它不包括用于获取这些边界的递归求解机制，这将在其他地方单独介绍。

Core questions

• 大O、大Omega和大Theta各自对函数增长有何断言？
• 为什么在渐近比较中忽略常数因子和低阶项？
• 常见的增长类别从最慢到最快是如何排序的？
• 渐近边界如何预测算法如何扩展到大型输入？
• 在实践中，渐近较慢的算法何时仍然更可取？

Key concepts

• 大O记法
• 大Omega记法
• 大Theta记法
• 小o和小omega
• 增长类别
• 常数因子
• 低阶项
• 可扩展性

Key theories

阶数记法

大O将函数限制在一个常数因子内的上界，大Omega将其限制在下界，大Theta则将其限制在双向；这些由克努特为计算机科学标准化的定义，为增长率提供了一种精确的语言。

增长率的主导性

随着输入规模的增长，高阶项占据主导地位，因此算法的渐近类别（例如线性对数与二次方）最终决定了其可扩展性，而与常数因子无关。

Clinical relevance

渐近记法是讨论算法效率的通用语言：它使工程师能够比较候选算法，预测系统是否能扩展以处理更大的工作负载，并在文档、面试以及库和标准的分析中传达性能保证。

History

大O及相关记法起源于19世纪分析数论中巴赫曼和兰道（因此称为“兰道记法”）的工作。唐纳德·克努特在20世纪60年代和70年代将其改编并标准化用于算法分析，包括1976年的一篇澄清计算机科学中大Omega和大Theta用法的文章。

Key figures

• Donald Knuth
• Paul Bachmann
• Edmund Landau

Seminal works

• knuth1976bigo
• cormen2009

Frequently asked questions

较小的大O总是意味着更快的算法吗？

对于给定的输入规模来说不一定。大O描述的是输入规模趋于无穷大时的增长，并隐藏了常数因子，因此渐近类别较差的算法在小输入上可能更快。它对于大输入和可扩展性是更好的指导。

大O和大Theta有什么区别？

大O只给出增长的上界，因此它表明算法不会比给定速率更差。大Theta给出紧密界，断言增长在上下两方面都与该速率匹配。说一个算法是Theta(n log n)比O(n log n)是一个更强、更精确的陈述。