大 O.

Big O 表示法为函数的增长提供了上限。直观的 f ∊ O(g)，f 增长最多快 g。

正式 f ∊ O(g) 当且仅当有一个正数 C 和一个正数``n 这样对于所有正数 m > n 我们有

C⋅g(m)> f(m)。

直觉这个定义

关于 C 的直觉

C 负责吞咽功能中的常数因素。如果 h 是 f 的两倍，我们仍然有 h ∊ O(g)，因为 C 可以是两倍大。为此，有两个基本原理：

• 更简单的符号：f ∊ O(n) 优于 f ∊ O(7.39 n)。
• 抽象：在这些考虑中吞下任何时间单位，因为它们没有任何好处; 它们在机器之间有所不同，算法可以免费评估。由于 C 吞噬了恒定因子，因此复杂性等级甚至在机器上保持相同的十倍速度。

关于 n 的直觉

n 负责吞咽初始湍流。一种算法可能具有初始化开销，这对于小输入来说是巨大的，但从长远来看会得到回报。n 的选择允许足够大的输入来获得焦点，而忽略初始拉伸。

关于 m 的直觉

m 的范围超过所有大于 n 的值 - 以形成“从 n 开始，这就成立”的想法。