什么是 Big-O 表示法

Big-O 表示法是用于谈论功能的长期增长率的符号。它经常用于算法分析，以讨论算法的运行时或空间复杂性等相关概念。

在常见用法中，使用 big-O 表示法来讨论算法的运行时如何按输入的大小进行缩放。例如，我们假设选择排序的运行时间为 O（n 2 ），因为运行时是作为要排序的数组大小的函数的二次方增长。也就是说，如果你将输入的大小加倍，则选择排序的运行时间应该大约加倍。使用 big-O 表示法时，惯例是删除系数并忽略低阶项。例如，虽然技术上说二进制搜索在时间 O（2 log 2 n + 17）中运行并没有错，但它被认为是糟糕的风格，并且最好在时间 O（log n）中编写二进制搜索运行。

形式上，big-O 表示法用于量化函数的长期行为。我们说 f(n)= O(g)（在某些来源中有时表示为 f(n)∈O（g(n)），如果有固定常数 c 和 n 0 ，则 f(n)≤c·g （N）对所有的 n≥ñ 0 。这个正式的定义解释了为什么我们不关心低阶项（它们可以通过使 c 更大并且增加 n 0 ）和常数因子（c 项吸收它们） 来归结。这种形式定义通常用于严格的算法分析，但很少用于口语。