文档介绍：第九章 算法分析与设计＊
算法与数据结构的关系
不了解施加于数据上的算法就无法决定如何构造数据；
反之算法的结构和选择又常常在很大程度上依赖于作为基础的数据结构。
算法＋数据结构＝程序
1
静态分析
动态分析
循环
递归
2
1。静态分析
求出算法中使用的所有变量的存储空间，再折合成多少空间单位即可。
void insertSort(SortObject * pvector)
{ int i, j;
RecordNode temp;
for( i = 1; i < pvector->n; i++ )
{ temp = pvector->record[i]; j = i-1;
while((<pvector->record[j].key)&&(j>=0))
{ pvector->record[j+1] = pvector->record[j];
j--;
}
if(j!=(i-1)) pvector->record[j+1] = temp;
}
}
3
2。动态分析
动态空间的确定主要由两种情况构成：
（1）函数的递归；
（2）调用动态分配（malloc）和回收（free）函数
（1）函数的递归；
递归深度为ｈ，动态空间代价为C*h
（2）调用动态分配（malloc）和回收（free）函数
主要考虑分配内存大小与规模无关的情况。这时空间代价由分配和回收的次数决定。
4
算法的执行时间绝大部分花在循环和递归上。
1。循环
循环语句的时间代价一般用以下三条原则分析：
对于一个循环，循环次数乘以每次执行简单语句的数目即为其时间代价。
对于多个并列循环，可先计算每个循环的时间代价，然后按大Ｏ表示法的加法规则计算总代价。
对于多层嵌套循环，一般可按大Ｏ表示法的乘法规则计算。但如果嵌套是有条件的，为精确计算其时间代价，要仔细累加循环中简单语句的实际执行数目，以确定其时间代价。
5
循环分析示例1：
int Index_KMP(SeqString t, SeqString p, int pos)
{ int i, j, *next;
next = (int *)malloc(sizeof(int)*(+1));
GetNext(p, next);
j = pos; i = 0;
while(i < && j < )
{ if(i == -1 || [i] == [j])
{ ++i; ++j;
}
else i = next[i];
}
free(next);
if(i >= ) return (j – +1); /* Found */
else return -1;
} /* end of Index_KMP() */
6
2。递归
对于递归算法，一般可把时间代价表示为一个递归方程。
a>d(b)：
7
a<d(b)：
a＝d(b)：
例 求快速排序法的时间代价。
解 此算法的递归方程可表示为：
T(n)＝２T(n/2)＋n，这里ａ＝２，ｂ＝２，d(x)＝ｘ是积性函数。因为ａ＝d(b)＝２，所以
8
最基本的算法设计技术：
分治法
贪心法
动态规划法
回溯法
9
分治策略是把一个规模为ｎ的问题分成两个或多个较小的与原问题类型相同的子问题，通过对子问题的求解，并把子问题的解合并起来从而构造出整个问题的解，即对问题分而治之。如果子问题的规模仍然相当大，仍不足以很容易地求得它的解，这时可以对此子问题重复地应用分治策略。
10