算法（algorithm） 是为求解一个问题需要遵循、被清楚地指定的简单指令集合。对于一个问题，一旦给定某种算法并且（以某种方式）确定其是正确的， 那么重要的一步就是就是确定该算法将需要多少时间或空间等资源量的问题。如果一个问题的求解算法需要长达一年时间，那么这种算法就很难有什么用处。同样，一个需要 1GB 内存的算法在当前的大多数机器上面也是没法使用的。
在这一章中将讨论：
- 如何估计一个程序所需要的时间。
- 如何将一个程序的运行时间从天或年降低到秒
- 粗心使用递归的后果
- 将一个数自乘得到其幂以及计算两个数的最大公因数的非常有效的算法。
数学基础
定义：如果存在正常数 $c$ 和 $n_0$ 使得当 $N \geq n_o$ 时 $T(N) \leq cf(N)$，则记为 $T(N) = O(f(N))$
定义：如果存在正常数 $c$ 和 $n_0$ 使得当 $N \geq n_o$ 时 $T(N) \geq cg(N)$，则记为 $T(N) = \Omega(g(N))$
定义：$T(N) = \Theta(h(N))$ 当且仅当 $T(N) = O(h(N))$ 且 $T(N) = \Omega(h(N))$
定义：如果 $T(N) = O(p(N))$ 且 $T(N) \neq \Theta(p(N))$ ， 则 $T(N) = o(p(N))$
这些定义的目的是要在函数之间建立一种相对的级别。给定两个函数，通常存在一些点，在这些点 上一个函数的值小于另一个函数的值，因此，像 $f(N) < g(N)$ 这样的声明是没有意义的。 于是，我们比较它们的相对增长率（relative rate of growth）。当将相对增长率应用到算法分析的时候，我们将会明白为什么它是重要的度量。
虽然 $N$ 较小时，$1000N$ 要比 $N^2$，但 $N^2$ 以更快的速度增长，因此 $N^2$ 最终将更大。在这种情况下，$N = 1000$ 是转折点。第一个定义是说，最后总会存在某点 $n_0$， 从它以后 $c \cdot f(N)$ 总是至少与 $T(N)$ 一样大，从而若忽略常数因子，则 $f(N)$ 至少与 $T(N)$ 一样大。在例子中，$T(N) = 1000N, f(N) = N^2, n_0 = 1000$ 而 $c = 1$。 我们也可以让 $n_0 = 10$ 而 $c = 100$。因此，我们可以说 $1000N = O(N^2)$（$N$ 平方级）。这种记法称为大 $O$ 记法。常常不说“…级的”，而是说“大 $O$ …”