1. 算法分析¶

算法 (algorithm) 是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。对于一个问题，一旦某种算法给定并且(以某种方式)被确定是正确的，那么重要的一步就是确定该算法将需要多少诸如时间或空间等资源量的问题。如果一个简单问题的求解算法竟然需要长达一年时间，那么这种算法就很难能有什么用处。同样，一个需要若干个GB (gigabyte) 的内存的算法在当前的大多数机器上也是无法使用的。

1.1. 数学基础¶

将有以下定义：

如果存在正常数 \(c\) 和 \(n_0\) 使得当 \(N \geqslant n_0\) 时 \(T(N) \leqslant cf(N)\) ，则记为 \(T(N) = O(f(N))\) 。【 \(T(N)\) 增长率小于等于 \(f(N)\) 】
如果存在正常数 \(c\) 和 \(n_0\) 使得当 \(N \geqslant n_0\) 时 \(T(N) \geqslant cg(N)\) ，则记为 \(T(N) = \Omega(f(N))\) 。【 \(T(N)\) 增长率大于等于 \(f(N)\) 】
\(T(N) = \Theta(h(N))\) 当且仅当 \(T(N) = O(h(N))\) 和 \(T(N) = \Omega(h(N))\) 。【 \(T(N)\) 增长率等于 \(f(N)\) 】
如果对每一正常数 \(c\) 都存在常数 \(n_0\) 使得当 \(N > n_0\) 时 \(T(N) < cp(N)\) ，则 \(T(N)=o(p(N))\) 。有时也可以说，如果 \(T(N) = O(p(N))\) 且 \(T(N) \neq \Theta(p(N))\) ，则 \(T(N) = o(p(N))\) 。【 \(T(N)\) 增长率小于 \(f(N)\) 】

这些定义的目的是要在函数间建立一种相对的级别。给定两个函数，通常存在一些点，在这些点上一个函数的值小于另一个函数的值，因此，一般地宣称，比如说 \(f(N)<g(N)\)，是没有什么意义的。于是，我们比较它们的 相对增长率( relative rate of growth )。当将相对增长率应用到算法分析时，我们将会明白为什么它是重要的度量。

虽然对于较小的 \(N\) 值 \(1000N\) 要比 \(N^2\) 大，但 \(N^2\) 以更快的速度增长，因此 \(N^2\) 最终将是更大的函数。在这种情况下，\(N= 1000\) 是转折点。第一个定义是说，最后总会存在某个点 \(n\)。从它以后 \(c·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……”。

当 \(T(N)=O(f(N))\) 时，我们是在保证函数 \(T(N)\) 是在以不快于 \(f(N)\) 的速度增长;因此 \(f(N)\) 是 \(T(N)\) 的一个上界( upper bound)。这意味着 \(f(N) = \Omega (T(N))\) ，于是我们说 \(T(N)\) 是 \(f(N)\) 的一个下界( lower bound )。

重要论据：

如果 \(T_1(N) = O(f(N))\) 且 \(T_2(N) = O(g(N))\)，那么
1. \(T_1(N)+T_2(N) = O(f(N)+g(N))\) (直观的可以认为 \(max(O(f(N)),O(g(N)))\))
2. \(T_1(N) * T_2(N) = O(f(N)*g(N)) \)
如果 \(T(N)\) 是一个 \(k\) 次多项式，则 \(T(N) = \Theta(N^k)\)
对于任意常数 \(k\) ， \(\log^k N = O(N)\)

1.2. 运行时间计算¶

为了简化分析，我们将采取如下约定：不存在特定的时间单位。因此，我们要抛弃一些前导的常数，还将抛弃低阶项，从而要做的就是计算大 \(O\) 运行时间。（即求上界）

法则1———for循环

一个for循环的运行时间至多是该for循环内部那些语句(包括测试)的运行时间乘以迭代的次数。

法则2——嵌套的for循环

从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积。

法则3——顺序语句

将各个语句的运行时间求和即可(这意味着，其中的最大值就是所得的运行时间)。

法则5—— if/else 语句

代码块 1.2.1 T=s1+s2¶

if(condition)
    s1
else
    s2

示例中的判断语句运行时间不会超过 s1 和 s2 的时间。