第一章 什么是算法
算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。
算法的三个要素
1).数据: 运算序列中作为运算对象和结果的数据.
2).运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移: 运算序列中的控制和转移. 算法分类
从解法上：数值型算法:算法中的基本运算为算术运算；非数值型算法:算法中的基本运算为逻辑运算.
从处理方式上：串行算法:串行计算机上执行的算法；并行算法:并行计算机上执行的算法 算法的五个重要的特性
（1） 有穷性：在有穷步之后结束。 （2） 确定性：无二义性。
（3） 可行性：可通过基本运算有限次执行来实现。
（4） 有输入 表示存在数据处理 （5） 有输出 伪代码
程序设计语言（PDL），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2)以自然语言的自由语法描述了处理过程；3)数据声明应该既包括简单的也包括复杂的数据结构；4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n阶方阵的相加C=A+B的算法如下，分析其时间复杂度。 #define MAX 20 //定义最大的方阶 void matrixadd(int n,int A[MAX][MAX], int B[MAX][MAX],int C[MAX][MAX]) { int i,j;
for (i=0;i 该算法中的基本运算是两重循环中最深层的语句C[i][j]=A[i][j]+B[i][j]，分析它的频度，即： T(n)= ??1??n?n?1?n*n?ni?0j?0i?0i?0n?1n?1n?1n?12 =O(n2) 分析以下算法的时间复杂度。 void func(int n) { int i=0,s=0; while (s s=s+i; } } 对于while循环语句，设执行的次数为m，i从0开始递增1，直到m为止，有： s=0+1+2+?+(m-1)=m(m-1)/2，并满足s=m(m-1)/2 有如下算法： void fun(int a[],int n,int k) //数组a共有n个元素 { int i; if (k==n-1) for (i=0;i n。T(n)=O(n) { for (i=k;i 调用上述算法的语句为fun(a,n,0)，求其时间复杂度。 设fun(a,n,0)的时间复杂度为T(n)，则fun(a,n,k)的执行时间为T1(n,k)，由fun()算法可知： T1(n,k)=n 当k=n-1时 T1(n,k)= (n-k)+T1(n,k+1) 其他情况 则： T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2) =?=n+(n-1)+?+2+T1(n,n-1) =n+(n-1)+ ?+2+n =O(n2) 所以调用fun(a,n,0)的时间复杂度为O(n2)。 估计如下二重循环算法在最坏情况下时间复杂性T(n)的阶。 for i:= 1 to n do for j:=1 to i do {s1,s2,s3,s4} ; s1,s2,s3,s4为单一赋值语句 分析:内循环体只需O(1)时间，故 内循环共需 ?O(1）?O(?1)?O(i)j?1j?1ii 外循环共需i?1?O(i)?O(?i)?O(i?1NNN(N?1))?O(N2)2 渐进分析 时间复杂性渐进阶分析的规则：(最坏情况) 1). 赋值，比较，算术运算，逻辑运算，读写单个变量（常量）只需1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1；a2: s2；...； am: sm 需要的时间为 max（TS1,TS2 ,..., TSm）. 4). 访问数组的单个分量或纪录的单个域需要一个单位时间. 5). 执行for循环语句的时间=执行循环体时间*循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数. 7). 用goto从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则1-7进行分析； 对递归调用，可建立关于T(n)的递归方程,求解该方程得到T(n). 插入排序算法的实现要点： （1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。 （2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。 每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。 （3）【关键代码】要考虑直接转换还是需要建立相应的独立函数。对于赋值和下标通常可以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。 归并排序算法的实现要点： （1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。 参数：序列A[p?r]的子序列A[p?q]和A[q+1?r]，可以表示为区间[p,q],[q,r] 指针（或迭代器）p，q，r：p指向第一个子序列的首元素，q指向第二个子序列首元素，r指向第二个子序列末尾元素之后，单个元素数据长度及比较函数指针。 返回值：无 （2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。 每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。 （3）【关键代码】要考虑直接转换还是需要建立相应的独立函数。 对于赋值和下标通常可以直接转换。 一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。 序列的划分算法的实现要点： （1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。 参数：A 是数组或序列p, r分别是整数或者迭代器 返回值：分界点位置的整数或者迭代器 （2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。 每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。 （3）【关键代码】要考虑直接转换还是需要建立相应的独立函数。 对于赋值和下标通常可以直接转换。 一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。 第二章 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 分治法的设计思想： 将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 分治策略在每一层递归包括3个步骤： 分解 将问题分解成若干个子问题。 治理 递归地解决各子问题。不过若子问题的规模足够小，就以直接的方式（不再递归）解决子问题。 合并 将子问题的解合并成原问题的一个解。 divide-and-conquer(P) { if ( | P | <= n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk；//分解问题 for (i=1,i<=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 } 分治法的复杂性分析： 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为O(1)n?1?T(n)???kT(n/m)?f(n)n?1通过迭代法求得方程|P|=n的问题所需的计算时间，则有： T(n)?n的解： logmk?logmn?1?kj?0jf(n/mj) 递归小结： 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为非递归，从而迭代求出结果。 二分搜索算法： template int BinarySearch(Type a[], const Type& x, int l, int r) { while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } return -1; } 算法复杂度分析： 每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。 第三章 动态规划算法总体思想： 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 分治法与动态规划的相同点： 分治法与动态规划，二者要求原问题具有最优子结构，都是将问题分而治之分解成若干个规模较小的子问题 。 不同点：分治法是将原问题分解为多个子问题，利用递归对各个子问题独立求解，最后利用各子问题的解进行合并形成原问题的解。分治法将分解后的子问题看成是相互独立的。动态规划是将原问题分解为多个子问题，通过计算出子问题的结果构造一个最优解。动态规划通过迭代法自底向上求解，动态规划将分解后的子问题理解为相互间有联系，有重叠的部分。 knapsack算法实现要点： （1）【参数和返回值】参数：物件个数n，重量数组W（一维整型），价值数组C（一维整型），背包容量C（整型）。 返回值：返回整型二维数组m （2）【数据设置】设置一个（n+1 ）×（c+1 ）二维数表m；循环控制变量i，j（整数） （3）【关键代码】伪代码结构清晰，容易实现。 Floyd算法实现要点： （1）【参数和返回值】参数：图的顶点个数n；图的邻接矩阵：浮点型矩阵w； 返回值：返回矩阵D和∏构成的数据结构 （2）【数据设置】两个二维数表d和pi（对应矩阵D和∏ ）；循环控制变量i， j，k（整数） （3）【关键代码】顶点从0～n-1编号。邻接矩阵D中∞用浮点型最大值代替；父结点矩阵∏中空指针NIL用-1表示；要输出路径还需要实现PRINT-ALL-PAIRS-SHORTEST-PATHS算法 第四章： 贪心算法：依赖于当前已经做出的所有选择，采用自顶向下（每一步根据策略得到当前一个最优解，保证每一步都是选择当前最优的）的解决方法。 贪婪算法设计的3个步骤： （1）分析问题的最优子结构 （2）分析问题的贪婪选择性质 （3）根据最优子结构和贪婪性质自顶向下计算最优解。 Huffman算法实现要点： （1）【参数和返回值】参数：字符集C及频数数组及个数；返回值：返回二叉树 （2）【数据设置】需要最小优先队列Q；循环控制变量i（整数） （3）【关键代码】需要先实现二叉树的数据结构 单源最短路径算法实现要点（与prim算法类似）： （1）【参数和返回值】参数：图形矩阵W（浮点型）及顶点数n （整型）及源点s（整型） 返回值：返回key和pi的数据结构 （2）【数据设置】需要浮点型数组d和整型数组pi，需要最小优先队列Q；需要顶点变量u和v（整数）