增长的秩

增长的秩，即增长的数量级，是对算法复杂度的度量。一般程序员熟悉的大 O 标记法，就是增长的秩的一种表示方法。

但是本书居然没有提及这种标记方法，而是采用了大 Θ 标记法。程序员们不禁要问，这两种标记法有什么区别？

先上结论：大 Θ 标记法提供的信息更多。

SICP 通过很多例子展示了不同算法的处理过程在消耗计算资源的速率上的巨大差异。它说要描述这种差异，有个简单的办法，就是使用增长的秩，来大致估计当输入变得更大时所需要的计算资源。精确定义如下：

使用 n 这个参数来描述问题的规模，用 R(n) 来表示处理过程为处理这个规模为 n 的这个问题所需要的资源的数量。对于指定的待分析的处理过程，其所处理的问题有很多个属性可以用作这个参数 n。比如要计算平方根的近似值，可以采用精确的小数位数作为 n；对于矩阵乘法，可以采用矩阵的行数作为参数 n 等等。类似地，R(n) 既可能是被使用到的存储寄存器的数量，也可能是执行的基本机器操作次数，等等。计算机在指定时间只会执行有限次数的操作，所以一个处理过程所需要的时间是和其执行的基本机器操作的次数成正比的。

大 Θ 标记法

当我们说 R(n) 具有 Θ(f(n)) 的增长秩时，记作 R(n) = Θ(f(n))，这就意味着存在两个独立于 n 的正常数 k₁ 和 k₂，它们对所有足够大的 n 满足如下关系：

k₁ f (n) ≤ R(n) ≤ k₂ f (n)

即，当 n 足够大时，R(n) 的值被夹逼在 k₁ f(n) 和 k₂ f(n) 之间，像个三明治一样。

以上对于大 Θ 标记的定义做了详细的介绍，现在我们知道它提供了一个函数的上下极限这两个信息，而大 O 标记提供的信息更少，就是因为它只提供了上极限，也就是只给出了算法的最坏表现。

大 O 标记法

当我们只有一个上限渐进值时，我们一般采用大 O 标记法，精确定义如下：

对给定的函数 g(n)，O(g(n)) 是这样的函数的集合：

O(g(n)) = {f(n) : 存在正常数 k 和 n₀，对所有大于等于 n₀ 的 n 都满足 0 ≤ f(n) ≤ k g(n)}。

它们的关系

• 所有的大 Θ 标记法都是大 O 标记法的子集。但反之不成立。
• T(n) 等价于 Θ(f(n))，如果它既是 O(f(n)) 的，又是 Ω(f(n)) 的话。

大 Θ 标记法比大 O 标记法提供的信息更多，所以只要可能，使用大 Θ 标记法将是更受推荐的，这也是为什么 SICP 这本书只使用了这个标记法的原因。

但是，使用大 Θ 标记法会更加困难，因为要证明大 O 成立会比证明大 Θ 成立更加简单。

比如，归并排序既是 O(n log n) 的，又是 Θ(n log n) 的，但同时还可以是 O(n²) 的，因为 n² 是更“大”的值。但是它不可能是 Θ(n²)，因为这个算法并不是 Ω(n²) 的。（这个来自某大佬的说明，我还没有理解…… 也许是这个大佬说错了，还有待进一步思考和学习）

大 Ω 标记法

理解了上述大 Θ 标记法和大 O 标记法后，理解大 Ω 标记法就很容易了。它给出了函数的下逼近值。即如果 T(n) 是 Ω(f(n)) 的，那么存在一个数 n₀ 和 k，使得 T(n) ≥ k f(n) 对于所有 n ≥ n₀ 成立。

总结

对于增长的秩（算法复杂度），有三种标记法，分别是大 Θ 标记法、大 O 标记法和大 Ω 标记法。他们都只给出了当输入很大时近似值。

• 大 Θ 标记法：给出了函数的上极限和下极限。
• 大 O 标记法：给出了函数的上极限。
• 大 Ω 标记法：给出了函数的下极限。

要注意的是，这三种标记法和算法复杂度分析中的最好、最坏以及平均情况是不同的，它们都可以用在每一种情况的分析中。