大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)

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

点击标题见原文详细。

 

猜你喜欢