Big-O 符号速查表：Big-O 问题的快速解答

本文由 Jerry Ejonavi 撰写。对 Big-O 符号感到好奇？今天，我们整理了一份快速指南，解答所有常见的 Big-O 符号问题。

大 O 符号（有时也称为 Big Omega）是程序员分析算法时间和空间复杂度的最基本工具之一。大 O 符号是一种用于衡量算法性能上限的渐近符号。

当您编写具有严格 SLA 的软件或大型程序时，算法和数据结构的选择至关重要。大 O 符号允许您比较算法性能，以找到最适合您特定情况的算法。大 O 评级有助于确保您的运行时间比竞争对手更短。

本文旨在快速解答您可能遇到的或在面试中遇到的有关大 O 符号的常见问题。

让我们开始吧！

以下是我们今天要讨论的内容：

什么是大 O 符号？

大 O 符号是计算机科学中用来描述算法复杂度的数学函数。它通常用来衡量算法执行所需的运行时间。

但是，它不会告诉您算法的运行速度有多快或多慢，而是告诉您算法的性能如何随着输入的大小（size n）而变化。

影响 Big O 的最大因素是程序在 for 循环等重复结构中采取的步数和迭代次数。

对于我们的正式定义，我们定义

O(g(n))

作为一组函数，如果函数f(n)满足以下条件，则可以成为该集合的成员：

0 ≤ f(n) ≤ cg(n)0 ≤ f(n) ≤ cg(n)

常数是一个正常数，当输入大小超过正阈值n0c时，不等式成立n

如果一个算法对大小为 n 的数组中的每个项目执行计算，我们可以说该算法运行在

在）

（或者它具有恒定的时间复杂度）并为每个执行以下工作：

O(1)

算法的时间复杂度量化了算法运行所需的时间，它是输入长度的函数。同样，算法的空间复杂度量化了算法运行所需的空间或内存，它是输入长度的函数。

两者都依赖于一些外部因素，例如计算机硬件、操作系统等，但在对算法进行分析时，这些因素都不会被考虑。

以下是一些常见的算法复杂性：

什么是函数？

函数是接受输入并返回输出的例程。它如下所示，其中输出根据输入定义n。
$f(n)=n^2$

排序算法	最坏的情况	平均情况	最佳情况
冒泡排序	$O(n^2)$	$O(n^2)$	$在）$
插入排序	$O(n^2)$	$O(n^2)$	$在）$
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$
快速排序	$O(n^2)$	$O（n log n）$	$O（n log n）$
合并排序	$O（n log n）$	$O（n log n）$	$O（n log n）$
堆排序	$O（n log n）$	$O（n log n）$	$O（n log n）$

注意：尽管最坏情况下的快速排序性能是二次的，但在实践中，快速排序经常用于排序，因为它的平均情况是对数的。

现在你已经掌握了 Big O 中的常见主题，应该可以充分准备应对遇到的大多数问题。我们还有一些其他更技术性的主题没有涉及，例如：

如果你想学习这些主题，可以看看 Educative 的课程《Big-O Notation For Coding Interviews and Beyond》。该课程用通俗易懂的语言解释了这些概念，并教你如何在不需要大量数学技能的情况下推理算法的复杂性。

学习愉快！