1.3 算法分析
算法分析主要是分析算法的执行时间和存储空间，它们是评判一个算法好与坏的重要指标。从执行时间上分析就是分析算法的时间复杂度；从存储空间上分析就是分析算法的空间复杂度。
1.3.1 算法的时间复杂度
算法的时间复杂度是指算法运行所需时间，一般将算法中的执行次数作为时间复杂度的衡量标准。时间复杂度函数记为T（n）=O（f（n））。
【算法1.3】分析下面算法中每条语句执行的次数，以及一共执行了多少次。
public void algorithm1_3() {
int sum = 0; //执行1次
int n = 9; //执行1次
int m = 9; //执行1次
for (int i = 1; i <= n; i++) { //外循环执行n+1次
for (int j = m; j >= 1; j--) { //内循环执行n*(m+1)次
System.out.println("我在循环之内！"); //执行n*m次
}
System.out.println(" 我在循环之间！"); //执行n次
}
System.out.println(" 我在循环之外！"); //执行1次
}
算法1.3展示了每条语句执行的次数，总共执行次数为1+1+1+（n+1）+n·（m+1）+n·m+n+1，令m=n，则T（n）=2n2+3n+5，当n足够大时，显然算法执行次数取决于第1项，后面2项可以忽略不计。
如果用时间复杂度的渐近上界表示，如图1.4所示，其对应的极限公式为
图1.4 时间复杂度的渐近上界
当n≥n0时，T（n）≤cf（n），cf（n）可看作T（n）的上界；当n足够大时，T（n）和f（n）近似相等，用O（f（n））表示时间复杂度的渐近上界，即表示时间复杂度。算法1.3的时间复杂度O（f（n））=O（n2），因为当f（n）=n2时，
满足公式。
还有时间复杂度渐近下界和时间复杂度渐近精确界两种情况，分别如图1.5和图1.6所示。我们通常用时间复杂度渐近上界O（f（n））来表示时间复杂度。时间复杂度的计算需要考虑3个因素：问题规模；语句频度；算法优化。
图1.5 时间复杂度的渐近下界
图1.6 时间复杂度的渐近精确界
1. 问题规模
O（f（n））中的n为问题规模。一般地，问题规模越大，时间复杂度越大，但也存在时间复杂度与问题规模无关的情形。
➢ 举例1：1个窗口，8人排队做检查。若平均每人做检查的时间为5s，则总的检查时间为40s；假设人数增加为800，则总的检查时间为4000s。显然，人数（即问题规模n）从8增加到800，总的检查时间将随之增加。
➢ 举例2：1000个窗口，不超过1000人做检查。检查的人不用排队，同时来也无妨。显然，只有1人做检查的时间：5s。1人和1000人做检查所花时间皆为5s。这种情形的时间复杂度与问题规模无关。
【算法1.4】做检查所花时间与问题规模之间的关系（假设检查1人需花时间5s）。具体代码如下。
public void algorithm1_4(int n, int windows) {
//n为问题规模，windows为窗口数
int totalTime = 0; //所花总时间，初始值为0
if (windows == 1) //只有1个窗口
while (n-- != 0) {
totalTime += 5; //执行n次
}
else if (windows >= n) //窗口数不少于人数
totalTime = 5; //执行1次
}
算法1.4展示了算法的时间复杂度与问题规模之间的关系。算法的时间复杂度也可能要取决于其他条件因素，具有不确定性，这里为窗口数：当窗口数大于或等于人数（问题规模）时，时间复杂度与问题规模无关；反之则相关。
一个算法的时间复杂度之所以具有不确定性，是因为其有最好情况、最坏情况和平均情况。判断一个算法好与坏，算法的时间复杂度最坏情况是主要考虑因素。
【思考与练习1.1】
✓ 举一些时间复杂度与问题规模无关的算法例子。
答：例如“秒抢”系统，系统设置了只过滤出5个名额，5000、5万、50万人去抢，执行时间都不受影响。
✓ 分析下面算法的时间复杂度与问题规模n是否相关。为什么？
public int thinkPad1_1(int n) { //n为问题规模
int x = 0, y = 0;
while (x < n) {
x++;
return y;
}
return x;
}
答：无关。因为无论问题规模是多少，算法中核心语句只执行1次。
2. 语句频度
语句频度是指语句重复执行的次数。我们在计算时间复杂度时，不必将每条语句执行的次数相加，一般只考虑执行次数最多的语句，如循环最内层的语句对时间复杂度贡献最大，这样的语句我们称为关键语句。在算法1.3中，“我在循环之内！”所在行语句对算法的时间复杂度贡献最大，故其执行次数可以代表该算法的时间复杂度。
3. 算法优化
实现同一个功能，采用不同的算法往往时间复杂度不同。
➢ 举例：毕业设计文档若干，包括论文和过程材料共11个；假设1个指导老师带了10个学生，师生共同打磨完成了所有文档；要求按照文档清单顺序装袋，装袋前师生在有些文档上须签字，每个袋子装1个学生的材料。如何高效完成装袋，不同算法思想其效率即时间复杂度是不一样的。
【思考与练习1.2】
✓ 针对上面的举例，分析下面的算法1和算法2的时间复杂度。若是你，会选择哪一种算法，为什么？
算法1：指导老师建11个文件夹，分别对应11种材料，如“任务书”“开题报告”“指导记录表”等，按材料归类，完成打印、签字、装订、装袋。
算法2：指导老师建10个文件夹，分别对应10个学生，如“888-张三”“999-李四”等，按学生归类，完成打印、签字、装订、装袋。
答：算法1描述如下。
Step1：新建11个材料文件夹。
Step2：10个学生的所有文档以材料文件夹归类。
Step3：按照文档清单顺序装袋要求，依次打印“任务书”“开题报告”“指导记录表”等文件夹中所有文档（这一步若以学生为单位打印，打印操作要跳转，烦琐）。
Step4：完成签字后，将纸质文档以学生为单位进行整理归类，装订并装袋。
算法2描述如下。
Step1：新建10个学生文件夹。
Step2：每个学生的所有文档放入其中。
Step3：按照文档清单顺序装袋要求，在打印每个学生文件夹材料时按装袋顺序打印。
Step4：完成签字后将纸质文档装订并装袋。
显然，算法2没有烦琐的打印操作跳转及打印后人工整理归类工作，节省了时间。
从上面的例子不难看出，优化算法就是减少算法的时间复杂度，正如学生从宿舍到教室，在很多条道路中选择最优的一条道路一样。根据算法的时间复杂度与问题规模的关系，可以将算法的时间复杂度按“阶”分为如下4类。
（1）常数阶：常数阶算法时间复杂度用O（1）表示，算法执行次数是个具体的常数，如1、3、10等。如思考与练习1.1中算法的执行次数为1，时间复杂度表示为O（1）。常数阶算法时间复杂度往往与问题规模无关。
（2）对数阶：对数阶算法时间复杂度用O（log n）表示，这种算法执行效率较高。如算法1.5是时间复杂度为对数阶的算法。
【算法1.5】时间复杂度为对数阶的算法。具体代码如下。
public void algorithm1_5(int n) {
int i = 1;
while (i <= n) {
i *= 2; //i呈倍数增长
}
}
在算法1.5中，i呈倍数增长，如1、2、4、8直到n，假设算法核心语句执行次数为x，则2x=n，推出x=log2 n，故该算法的时间复杂度表示为O（log2 n）。
（3）多项式阶：多项式阶算法时间复杂度用O（n）、O（n2）、O（n3）等表示，是较常见的时间复杂度算法。如算法1.6，将算法1.5中的“i*=2”改成“i+=2”，就成为时间复杂度为多项式阶的算法。
【算法1.6】时间复杂度为多项式阶的算法。具体代码如下。
public void algorithm1_6(int n) {
int i = 1;
while (i <= n) {
i += 2; //i以步长2增长
}
}
在算法1.6中，i以步长2增长，如1、3、5、7直到n，假设算法核心语句执行次数为x，则
，故算法1.6的时间复杂度可表示为O（n）。
【思考与练习1.3】
✓ 计算下面算法的时间复杂度。
public void thinkPad1_3(int n) {
int i, j, k;
int[][] c = new int[100][];
int[][] a = new int[100][];
int[][] b = new int[100][];
for (i = 0; i < n; i++) { //频度为n+1
for (j = 0; j < n; j++) { //频度为n* (n+1)
c[i][j] = 0; //频度为n* n
for (k = 0; k < n; k++) //频度为n* n*(n+1)
c[i][j] = c[i][j] + a[i][k] * b[k][j]; //频度为n* n*n
}
}
}
答：上面的算法用了3层循环，最内层循环中语句的频度为n3，故该算法的时间复杂度为O（n3）。
（4）指数阶：指数阶算法时间复杂度用O（2n）、O（n!）、O（nn）等表示，是算法设计的“恶梦”，我们要尽量避而远之。f（n）成了爆炸增量函数，问题规模增大一点点就会引起时间复杂度暴增。如算法1.7是时间复杂度为指数阶的算法。
【算法1.7】时间复杂度为指数阶的算法。具体代码如下。
public int algorithm1_7(int n) {
if (n <= 1)
return 1;
else
return algorithm1_7(n - 1) + algorithm1_7(n - 2); //递归调用
}
算法1.7是斐波那契数列算法，显然T（0）=T（1）=1，T（n）=T（n-1）+T（n-2）+1，通过归纳证明法可以证明，当n≥1时
，故该算法的时间复杂度可表示为O（2n）。
不同算法时间复杂度耗费时间的递增关系为O（1）<O（log2 n）<O（n）<O（n·log2 n）<O（n2）<O（n3）<O（2n）<O（n!）<O（nn）。
1.3.2 算法的空间复杂度
算法的空间复杂度是指算法及其执行所占用的存储空间。空间复杂度函数记为S（n）=O（f（n））。算法的空间复杂度包含以下3方面。
（1）算法本身所占存储空间。
（2）输入/输出数据所占存储空间。
（3）额外需要的辅助存储空间。
算法本身所占存储空间可以忽略不计；输入/输出数据所占存储空间根据题意往往是固定的；额外需要的辅助存储空间才是算法的空间复杂度的衡量标准。
➢ 举例：期末高等数学考试需要草稿纸，倘若监考老师要求每一个交卷的学生将草稿纸扔到门口边的一个垃圾桶里，监考老师就节省了从桌上收草稿纸的时间，而只需收试卷，但增加了辅助存储空间：垃圾桶。在这个例子中，以增加空间换取时间，这是算法设计中常采用的思路。
对于算法的空间复杂度，我们需要注意以下两点。
（1）算法的空间复杂度主要看算法所需的辅助存储空间个数。
（2）随着问题规模增加，所需的辅助存储空间个数是否增加？若不增加则空间复杂度为O（1）；否则看其与问题规模的关系，或为O（n）或为O（n2）等。
下面我们来分析算法1.8和算法1.9的空间复杂度。
【算法1.8】分析交换2个数的算法的空间复杂度。具体代码如下。
public void algorithm1_8(int x, int y) {
int temp; //辅助空间
temp = x;
x = y;
y = temp;
}
在算法1.8中，2个数的交换过程借助一个临时变量temp进行缓存得以完成，如图1.7所示。空间复杂度为O（1）。
图1.7 2个数的交换过程
【算法1.9】分析求n!的算法的空间复杂度。具体代码如下。
public int algorithm1_9(int n) {
if (n == 1)
return 1;
return n * algorithm1_9(n - 1); //递归调用
}
算法1.9，运用递归思想实现求n的阶乘，其实现过程可分为两大步骤：大问题分解为小问题进栈保存；出栈返回计算结果。以n=5为例，进栈出栈过程如图1.8所示。
图1.8 递归法求5的阶乘进栈出栈过程
从图1.8不难看出，出栈时f（1）=1已知，故返回时依次可求出：f（2）=2，f（3）=6，f（4）=24，f（5）=120。递归法借助栈作为辅助存储空间，求n！递归时会占用栈的n个存储空间，因此，其空间复杂度为O（n）。
【思考与练习1.4】
✓ 分析下面求二维数组元素之和算法的空间复杂度。
void thinkPad1_4(int[][] A, int[][] B, int[][] C, int n) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = A[i][j] + B[i][j]; //数组元素求和
}
答：O（1）。因为二维数组C所占存储空间是辅助存储空间且是固定的，与问题规模无关。
分析算法的空间复杂度分析时，一般不考虑形式参数所占存储空间，而只考虑临时变量所占存储空间。若一个算法所需临时存储空间相对于问题规模来说是常数，则该算法的空间复杂度为O（1），称此算法为原地工作或就地工作。