算法就是一系列解决问题的指令，对于给定的输入，能够在有限时间内获得预期的输出。一个好的算法和一篇好的文章一样，都是不断努力，反复修正的结果。算法分析主要从运行时间和存储空间两方面讨论算法的效率。相信有些人会有这样的感觉，对于一些算法，有时一眼就能看出它的时间复杂度，但就是无法比较规范的表达出来。本文就系统的整理一下如何规范推导算法的时间和空间复杂度。
算法分析的一个依据是，输入规模（又称问题规模，记为 n），根据直觉，程序的运行时间随着问题规模的增大而变长。那么怎么衡量程序的运行时间呢？其实程序大部分时间只花在某些重要的操作（指令）上，比如大部分排序基本操作就是比较交换，所以另一个依据就是，程序基本操作执行的次数。如果把基本操作的次数记为 f(n) ，每次执行的时间为 Cop 那么可以用以下公式估算运行时间 :
假设 f(n)=n(n-1)/2，那么如果输入规模翻倍，算法大约要运行 4 倍的时间，这是因为当 n 值足够大时，就有：
那么：
从上面的推导中可以看到，一些常量如Cop被忽略了。对于大规模的输入，比较大小（T(2n) > T(n)）是没有意义的，有意义的是程序运行时间的增长速度，也就是其时间函数的增长率。虽然在 n 比较小时 100n 要比 n2 大，但n2增长速度更快，总会存在一个点n0使得100n≤n2（这里这个点就是n=100）。
为了更方便的描述 T(n) 的增长数量级，使用”大O”来表示增长数量级的上限（也可以说是算法性能的渐进上限），其数学定义是：对于T(n)和f(n)，如果存在常数 C 和 n0 使得当n≥n0时，都有 0≤T(n)≤C×f(n)，则记为T(n)=O(f(n))。所以，我们可以认为100n=O(n2)。大O符号的两个规则：（1）算法由两个连续的执行部分组成，则 T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))。（2）算法有嵌套的操作，则T(n)=O(f(n) * g(n))。此外还有”大Ω”用来表示最坏情况下的性能下限；”大θ”用来描述算法的最优性能；定义和上面的差不多。在算法分析中，常见的增长数量级如下：
表1 常见增长数量级
| 数量级 | 描述 | 说明 | 典型代码 |
| O(1) | 常数级别 | 普通语句 | a = b + c |
| O(logN) | 对数级别 | 二分策略 | 二分查找 |
| O(N) | 线性级别 | 循环 | 遍历一维数组 |
| O(NlogN) | 线性对数级别 | 分治 | 归并排序 |
| O(N2) | 平方级别 | 双层循环 | 冒泡排序 |
| O(N3) | 立方级别 | 三层循环 | 检查所有三元组 |
| O(2n) | 指数级别 | 穷举查找 | 检查所有子集 |
大多数Java语句运行时间均为常数级别，而对数级别的增长率仅比常数时间的程序稍慢，对数的底和增长率无关（因为底数仅相当于一个常量因子），一般使用logN表示；线性级别比较常见于循环中；平方级别的程序一般含有两个嵌套的 for 循环，典型程序有冒泡，插入，选择排序；立方级别一般为三层嵌套for循环；指数级别的算法运行的非常慢，但仍然有其用武之地。
图 1 函数增长率
图1 来自算法第4版，与之对应的还有一个标准图像。关于对数图像，我认为，取对数其实就是对原始数据进行转换，由于对数的刻度比较小，呈现的图像更易于我们分析。图中各函数的增长率非常明显，在解决问题时，如果能够使用对数级别，线性级别或者线性对数级别的算法那是是最好不过了。
接下来通过一些常用算法的时间复杂度，来总结分析算法的常规步骤。
例1 斐波那契数列，其定义如下：
其中有两种常用的算法，递归和非递归算法，我们一一分析其中的时间复杂度。
（1）非递归算法
if(n==0 || n==1) return n;
int n0 = 0, n1 = 1; // n为0,1时的初值
int res = 0;
while(n >= 2){
res = n0 + n1;
n0 = n1;
n1 = res;
n--;
}
return res;
问题规模就是 n ，基本操作是 n--，假设其执行次数为 T(n)，那么可知 n-T(n)≥2，即T(n)≤n-2，所以T(n)=O(n)。
或者使用以下公式推导：
（2）递归算法
fib(int n) {
if(n==0 || n==1) return n;
return fib(n-1) + fib(n-2);
}
一般递归程序使用公式进行递推，由 T(n)=T(n-1)+T(n-2) 可以导出 T(n)-T(n-1)-T(n-2)=0，显然它是一个二阶常系数线性齐次递推方程（也称差分方程），它的特征方程为 x2-x-1=0，特征根分别为(1±√5)/2，根据初始条件 T(0)=T(1)=1，可得 T(n)=1/√5((1+√5)/2)n+1 - 1/√5((1+√5)/2)n+1 可以看出 T(n) 是以指数级别增长的。
例2 求 n 的阶乘
int fact(int n){
if(n==0) return 1;
return n * fact(n-1);
}
这也是递归，则 T(n)=n*T(n-1)，这个算法的基本操作是乘法，显然 n 的值从n变化到了0（其实还可以观察判断n是否等于0，判断了多少次）总共经过了n次，所以其时间复杂度为O(n)。怎么根据公式递推呢？假设进行了 T(n) 次乘法，则T(n)=T(n-1)+1（加1是因为最后要乘以n），使用反向替换法可知：
T(n) = T(n-1)+1 = T(n-2)+1+1 = T(n-2)+2=T(n-3)+1+2 = T(n-3)+3 = … = T(n-i)+i = … = T(n-n)+n = n
例3 选择排序
selection_sort(int a[], int n){
int i, j;
int min;
for(i=0; i<n; i+=){
min = i;
for(j=i+1; j<n; j++)
if(a[j]<a[min]) min = j;
swap(a[i], a[min]);
}
}
问题的规模为n，数组大小，基本操作一般位于最内层循环，这里就是比较大小，从内到外可以用以下公式表示比较的次数：
总结
对于大多数程序，一般可以用以下步骤：（1）确定问题规模；（2）找出基本操作；（3）计算执行次数，这里可能需要一些技巧或者数学分析。这里把程序分为递归和非递归两类来讨论。
1. 非递归程序
（1）如果基本操作中有变量参与循环条件的判断，那么我们可以找出 T(n)与循环变量的关系，带入条件中计算。比如以下程序判断
int i=1;
while(i<n)
i=i*2;
其中基本操作是 i=i*2，假设执行次数为T(n)，那么 i=2T(n) ，所以 2T(n)≤n，即 T(n)≤log2n，所以时间复杂度为O(logn)。
（2）还有一种与循环变量无关，这样的相对简单，直接统计次数，利用一些求和公式，因为大O只是一种上限，分析时可以适当的忽略一些数列。
2. 递归程序
递归程序的推导比较麻烦，但也有方法可循，如果可以根据公式，建立一个关于执行次数的递推公式以及初始条件，那么就可以确定它的增长次数，比如在求n的阶乘时的递推公式。
（1）反向替换法
对于 T(n)，用 T(n-1) 表达为 T(n-2) 的函数，然后带入原方程，把 T(n) 表示为 T(n-2) 的函数，对 T(n-2) 重复此操作，把 T(n) 表示为 T(n-3) 的函数，对于大部分的递推关系来说，能够呈现一种模式，并能够表示为 T(n-i) 的函数，其中 i=1, 2, …，最后选择合适的 i，使得 n-i 能够落入初始条件的定义域，再使用一种标准的求和公式，一般都能得到该递推公式的解。
假设有递推公式 T(n)=T(n-1)+n, 其中n>0，并且T(0)=0，那么可以这样进行推导。
① 使用 n-1 代替 n，得 T(n-1)=T(n-2)+n-1，带入原始方程得，T(n)=[T(n-2)+n-1]+n=T(n-2)+(n-1)+n
② 使用 n-2 代替 n，的 T(n-2)=T(n-3)+n-2，带入上一个方程得，T(n)=[T(n-3)+n-2]+(+n-1)+n=T(n-3)+(n-2)+(n-1)+n
③ 比较这三个公式，在第 i 次时，T(n)=T(n-i)+(n-i+1)+(n-i+2)+…+n
④ 初始条件为 n=0，所以n-i=0，i=n，则 T(n)=T(0)+1+2+…+n=n(n+1)/2
对于简单的递推关系，反向替换法比较好用。
待补充
附 1 算法分析中的实用公式
