Big-O 表示法

定义

Big-O 表示法的核心是数学符号，用于比较函数的收敛速度。让 n -> f(n) 和 n -> g(n) 成为自然数上定义的函数。然后我们说 f = O(g) 当且仅当当 n 接近无穷大时 f(n)/g(n) 有界。换句话说，f = O(g) 当且仅当存在常数 A 时，对于所有 n，f(n)/g(n) <= A。

实际上，Big-O 表示法的范围在数学上有点宽泛，但为了简单起见，我将其缩小到算法复杂度分析中使用的范围：在自然界定义的函数，具有非零值的函数，以及 n 增长的情况到无穷远。

这是什么意思？

我们来看一下 f(n) = 100n^2 + 10n + 1 和 g(n) = n^2 的情况。很明显，这两个函数都倾向于无穷大，因为 n 倾向于无穷大。但有时知道限制是不够的，我们也想知道功能接近极限的速度。像 Big-O 这样的概念有助于通过收敛速度来比较和分类函数。

让我们通过应用定义来找出 f = O(g)。我们有 f(n)/g(n) = 100 + 10/n + 1/n^2。由于当 n 为 1 并且正在减小时 10/n 为 10，并且由于当 n 为 1 并且还在减小时 1/n^2 为 1，所以我们有 f(n)/g(n) <= 100 + 10 + 1 = 111。定义是满意的，因为我们已经找到了 f(n)/g(n)（111）和 f = O(g) 的界限（我们说 f 是 n^2 的 Big-O）。

这意味着 f 在与 g 大致相同的速度下倾向于无穷大。现在这似乎是一件奇怪的事情，因为我们发现 f 最多比 g 大 111 倍，换句话说，当 g 增长 1 时，f 增长最多为 111.这似乎在增长快 111 倍并不是大致相同的速度。事实上，Big-O 符号并不是一种非常精确的方法来对函数收敛速度进行分类，这就是为什么在数学中我们在需要精确的速度估计时使用等价关系 。但是为了在大速度类中分离算法，Big-O 就足够了。我们不需要将相互之间生成固定次数的函数分开，而只需要无限增长的函数 ** 比彼此快。举例来说，如果我们采取 h(n) = n^2*log(n)，我们看到 h(n)/g(n) = log(n) 趋向于无穷大与正因此 h 是不为 O（n ^ 2），因为^ h 成长无限小于 n ^ 2 更快。

现在我需要做一个旁注：你可能已经注意到，如果 f = O(g) 和 g = O(h)，那么 f = O(h)。例如在我们的例子中，我们有 f = O(n^3) 和 f = O(n^4) …在算法复杂度分析中，我们经常说 f = O(g) 意味着 f = O(g) 和 g = O(f)，可以理解为“g 是 f 的最小 Big-O”。在数学中我们说这些函数是彼此的大相互作用。

怎么用？

在比较算法性能时，我们对算法执行的操作数感兴趣。这称为时间复杂度。在这个模型中，我们认为每个基本操作（加法，乘法，比较，赋值等）需要一定的时间，我们计算这些操作的数量。我们通常可以将此数字表示为输入大小的函数，我们称之为 n。遗憾的是，这个数字通常会随着 n 增长到无穷大（如果没有，我们说算法是 O(1)）。我们在 Big-O 定义的大速度类中分离我们的算法：当我们谈论“O（n ^ 2）算法”时，我们的意思是它执行的操作数，表示为 n 的函数，是 O（ N ^ 2）。这表示我们的算法大致与算法一样快，该算法可以执行大量等于其输入大小的平方的算法，或更快。 或更快部分是因为我使用 Big-O 而不是 Big-Theta，但通常人们会说 Big-O 意味着 Big-Theta。

在计算操作时，我们通常会考虑最坏的情况：例如，如果我们有一个最多可以运行 n 次且包含 5 次操作的循环，那么我们计算的操作数就是 5n。也可以考虑平均案例复杂性。

快速说明：快速算法是执行少量操作的算法，因此如果操作数量增长到无限快，则算法速度较慢 ：O(n) 优于 O（n ^ 2）。

我们有时也对算法的空间复杂性感兴趣。为此，我们将算法占用的内存中的字节数视为输入大小的函数，并以相同的方式使用 Big-O。