复杂度

在本书的不同地方，我们对一个算法需要多少次运算感兴趣。这些操作取决于上下文，但通常我们计算加法（或减法）和乘法。这被称为一个算法的算术或计算复杂性。例如，对$n$数字求和需要$n-1$次加法。另一个我们可能想要描述的数量是需要的空间（计算机内存）的数量。有时，容纳一个算法的输入和输出的空间就是全部需要的，但有些算法需要临时空间。所需的总空间被称为一个算法的空间复杂度。

算术复杂度和空间复杂度都取决于对输入的一些描述，例如，对于一个数组的求和，只需要数组的长度$n$。我们用 “数组求和的时间复杂度为$n-1$，其中$n$为数组的长度 “来表达这种依赖关系。

求和算法所花费的时间（或空间）并不依赖于其他因素，如数字的值。相比之下，一些算法，如计算整数阵列的最大公除数，可能取决于实际数值。

练习 14.1 将两个大小为$n\times n$的正方形矩阵相乘的时间和空间复杂度是多少？假设加法和乘法花费的时间相同。

通常我们的目的是简化描述时间或空间复杂性的公式。例如，如果一个算法的复杂度是$n^2+2n$，我们可以看到，对于$n>2$，复杂度小于$2n^2$，对于$n>4$，复杂度小于$(3/2)n^2$。另一方面，对于所有的$n$值，其复杂度至少为$n^2$。显然，二次项$n^2$是最重要的，而线性项$n$按比例变得越来越不重要。我们非正式地表示，当$n\rightarrow \infty$时，复杂度对$n$是二次的：存在常数$c$，$C$，所以对于$n$足够大时，复杂度至少是$cn^2$，最多是$Cn^2$。

简而言之，就是复杂度为$n^2$，当$n\rightarrow \infty$时，写为$O(n^2)$。在第四章中，我们会看到想要描述的现象是一个归零的参数的阶数。在这种情况下，例如我们写成$f(h)=O(h^2)$，当$h\downarrow 0$时，意味着$f$被$ch^2$和$Ch^2$所约束，对于某些常数$c$、$C$和$h$足够小。