大O表示法和Bachmann-Landau家族 - mariocervera

20-11-29 banq

我们大多数人（软件工程师）都熟悉（或至少听说过）著名的“ Big O”表示法（简称大O表示法、大O符号）。原因多种多样。大O符号是在技术面试中经常出现的概念，因此我们很可能在职业生涯的某个时候遇到大O符号。我们也可以简单地喜欢理论计算机科学，也可以在与算法的设计和分析相关的领域中工作。
大O表示法使您可以表征算法的渐近效率，可以描述算法的运行时间和所需的内存如何随输入的大小增加，随着输入的大小无限制地增长。
例如，您可以说选择排序的最坏情况下的运行时间为O（n²）。非正式地，这意味着选择排序的运行时间由n的二次函数从上方限制，其中n是输入的大小。
但是，本文的重点不是解释大O表示法。在这里，我假设您对大O表示法有基本的了解，并且我专注于这种表示法的鲜为人知的方面。
您是否知道O符号是更广泛的相关符号系列的一部分？
这个家族称为：Bachmann-Landau表示法。
有大量宝贵的资源详细介绍了Bachmann-Landau符号。例如，在这些书中：
  • 算法简介（第3版）。科尔曼，托马斯·H。莱斯森（Charles E.）；Rivest，罗纳德·L。斯坦·克利福德。麻省理工学院出版社（2009）。
  • 算法设计手册（第2版）。Skiena，Steven S.Springer（2008）。

您会找到正式的定义，详细的示例，练习以及什至我在此未介绍的其他符号。
在本文中，我将重点介绍巴合曼－朗道家族的三种符号：
  • O (Big O)
  • Ω (Big Omega)
  • ϴ (Big Theta)

我的这些符号的描述是故意非正式的。我的目标只是让您了解这些符号的含义以及它们为何有用。

点击标题见原文详细。