算法分析与设计

1、第一章什么是算法算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。算法的三个要素1）.数据 ：运算序列中作为运算对象和结果的数据 ?2）.运算 ：运算序列中的各种运算 ：赋值 ,算术和逻辑运算3）.控制和转移 ：运算序列中的控制和转移 .算法分类从解法上：数值型算法 ：算法中的基本运算为算术运算；非数值型算法：算法中的基本运算为逻辑运算 .从处理方式上：串行算法：串行计算机上执行的算法；并行算法：并行计算机上执行的算法算法的五个重要的特性（ 1） 有穷性 : 在有穷步之后结束。

2、（ 2） 确定性 : 无二义性。（ 3） 可行性 : 可通过基本运算有限次执行来实现。（ 4） 有输入f表示存在数据处理（5） 有输出A伪代码程序设计语言（ PDL ），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。特点： 1） 使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征；2） 以自然语言的自由语法描述了处理过程；3）数据声明应该既包括简单的也包括复杂的数据结构； 4） 使用支持各种模式的接口描述的子程序定义或者调用技术。求两个 n 阶方阵的相加 C=A+B 的算法如下，分析其时间复

3、杂度。#define MAX 20/定义最大的方阶void matrixadd (int n,int AMAXMAX, int BMAXMAX,i nt CMAXMAX) int i,j;for (i=0;i <n ;i+)for (j=0;j< n;j+)Cij=Aij+Bij;该算法中的基本运算是两重循环中最深层的语句Cij=Aij+Bij ，分析它的频度，即 :n 1 n 11n n 1 n* n2T( n) = i 0j 0ni 0i 0=0( n2)分析以下算法的时间复杂度。void fun c(i nt n) int i=0,s=0;while (s<n) i+;

4、 s=s+i; 对于 while 循环语句，设执行的次数为m, i 从 0 开始递增 1 直到 m 为止，有：s=0+1+2+(m-1)=m(m-1)/2，并满足s=m(m_1)/2<n ，则有m v n。T(n)=0( n)所以，该算法的时间复杂度为0( n )。有如下算法：void fun (int a,int n,int k) /数组 a 共有 n 个元素 int i;if (k=n-1)for (i=0;i<n;i+)/n 次prin tf("%dn",ai);else for (i=k;i<n;i+)/n-k 次ai=ai+i*i;fun (a

5、,n ,k+1);调用上述算法的语句为fun (a ,n ,0) ，求其时间复杂度。设 fun(a,n,0) 的时间复杂度为T(n) , 贝 U fun(a,n,k) 的执行时间为 T1(n,k) ，由 fun() 算法可知 :T1(n,k)=n 当 k= n-1 时T1(n,k)= (n-k)+T1(n,k+1)其他情况贝 U: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) 的时间复杂度为0(n2) 。 估计如下二重循环算法在最坏情

6、况下时间复杂性T(n) 的阶。for i:= 1 to n dofor j:=1 to i dos1,s2,s3,s4 ; s1,s2,s3,s4为单一赋值语句分析 ：内循环体只需O(1) 时间，故内循环共需渐进分析iiNNO(1 O( 1) O()()2O(i)O( i)O(Nj 1j 1。 呼 )外循环共需 1i 1时间复杂性渐进阶分析的规则：( 最坏情况 )1).赋值，比较，算术运算，逻辑运算，读写单个变量( 常量 ) 只需1 单位时间2).执行条件语句if c then S1 else S2的时间为TC +max(TS1,TS2).3).选择语句case A of a1: s1 ;a2

7、: 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）【参数和返回值】确

8、定输入数据个数和数据类型，输出个数和数据类型，数据的组织形欢迎下载2式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。（2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。（3） 【关键代码】要考虑直接转换还是需要建立相应的独立函数。对于赋值和下标通常可以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命

9、令或函数来实现。归并排序算法的实现要点：（1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。参数：序列 Apr的子序列 Apq和 Aq+1r，可以表示为区间 p,q,q,r指针（或迭代器） p, q,r： p 指向第一个子序列的首元素，q 指向第二个子序列首元素，r指向第二个子序列末尾元素之后，单个元素数据长度及比较函数指针。返回值：无（2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。每个变量都要考虑它的数据类型、存储结构、访问控制（局部变

10、量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。（3）【关键代码】要考虑直接转换还是需要建立相应的独立函数。对于赋值和下标通常可以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。序列的划分算法的实现要点：（1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。参数： A 是数组或序列 p, r 分别是整数或者迭代器返回值：分界点位置的整

11、数或者迭代器（2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。（3）【关键代码】要考虑直接转换还是需要建立相应的独立函数。对于赋值和下标通常可以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。第二章直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。分治法的设计思想：将一个难以直接解决的大问题，分割成一些规

12、模较小的相同问题，以便各个击破，分而治之。欢迎下载3分治策略在每一层递归包括3 个步骤：分解 将问题分解成若干个子问题。治理 递归地解决各子问题。不过若子问题的规模足够小，就以直接的方式( 不再递归 ) 解决子问题。合并 将子问题的解合并成原问题的一个解。divide-a nd-c onq uer(P)if ( | P | <= nO) adhoc(P);/解决小规模的问题divide P into smaller subinstances P1,P2,.,Pk； / 分解问题for (i=1,i<=k,i+)yi=divide-and-conquer(Pi); /递归的解各子问题

13、return merge(y1,.,yk);II 将各子问题的解合并为原问题的解分治法的复杂性分析：一个分治法将规模为n 的问题分成 k 个规模为 n/ m 的子问题去解。设分解阀值n0=1 ，且 adhoc 解规模为1 的问题耗费 1 个单位时间。再设将原问题分解为k 个子问题以及用merge将 k 个子问题的解合并为原问题的解需用f(n) 个单位时间。用T(n) 表示该分治法解规模为T(n)n1kT( n/m)1 通过迭代法求得方程|P|=n 的问题所需的计算时间，则有:f(n) nlog m kbg m nT(n)n m的解：递归小结：优点：结构清晰，可读性强,而且容易用数学归纳法来证明

14、算法的正确性,因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法<多。解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2、用递推来实现递归函数。3、通过变换能将一些递归转化为非递归，从而迭代求出结果。二分搜索算法：template<class Type>int Bin arySearch(Type a, const Type & x, int l, i

15、 nt r)while (r >= l)int m = (l+r)I2;if (x = am) return m;if (x < am) r = m-1;else l = m+1;return -1;欢迎下载4算法复杂度分析：每执行一次算法的while 循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要0(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。第三章动态规划算法总体思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。 不同

16、子问题的数目常常只有多项式量级。 在用分治法 求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案， 而在需要 时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。分治法与动态规划的相同点：分治法与动态规划，二者要求原问题具有最优子结构， 都是将问题分而治之分解成若干个规模较小的子问题 。不同点：分治法是将原问题分解为多个子问题， 利用递归对各个子问题独立求解， 最后利用 各子问题的解进行合并形成原问题的解。 分治法将分解后的子问题看成是相互独立的。 动态 规划是将原问题分解为多个子问题， 通过计算出子问题的结果构造一个最优解。 动态规划通 过迭代法自底向

17、上求解，动态规划将分解后的子问题理解为相互间有联系，有重叠的部分。knapsack 算法实现要点：(1)【参数和返回值】参数：物件个数n, 重量数组W ( 一维整型) ，价值数组C ( 一维整型) ，背包容量C ( 整型 ) 。返回值：返回整型二维数组m(2) 【数据设置】设置一个 ( n+1 ) x( c+1 ) 二维数表 m; 循环控制变量 i, j ( 整数 )(3) 【关键代码】伪代码结构清晰，容易实现。Floyd 算法实现要点：(1)【参数和返回值】参数：图的顶点个数n; 图的邻接矩阵：浮点型矩阵w;返回值：返回矩阵D 和 n 构成的数据结构(2)【数据设置】两个二维数表d 和 pi

18、 ( 对应矩阵 D 和 n ); 循环控制变量 i,j,k ( 整数 )(3)【关键代码】顶点从0? n-1 编号。邻接矩阵D 中 R 用浮点型最大值代替；父结点矩阵n 中空指针 NIL 用 -1 表示；要输出路径还需要实现PRINT-ALL-PAIRS-SHORTEST-PA算法第四章：贪心算法：依赖于当前已经做出的所有选择，采用自顶向下 ( 每一步根据策略得到当前一个最优解，保证每一步都是选择当前最优的) 的解决方法。贪婪算法设计的 3 个步骤：( 1 ) 分析问题的最优子结构( 2) 分析问题的贪婪选择性质( 3 ) 根据最优子结构和贪婪性质自顶向下计算最优解。Huffman 算法实现要

19、点：(1)【参数和返回值】参数：字符集C 及频数数组及个数；返回值：返回二叉树(2)【数据设置】需要最小优先队列Q; 循环控制变量 i ( 整数 )(3) 【关键代码】需要先实现二叉树的数据结构欢迎下载5单源最短路径算法实现要点( 与prim 算法类似 ) ：(1)【参数和返回值】参数：图形矩阵W ( 浮点型 ) 及顶点数n( 整型 ) 及源点 s ( 整型 )返回值：返回key 和 pi 的数据结构(2)【数据设置】需要浮点型数组d 和整型数组 pi, 需要最小优先队列 Q; 需要顶点变量 u 和 v ( 整数 )（ 3）【关键代码】需要先实现动态优先队列广度优先搜索 BFS 算法实现要点：

20、（1） 【参数和返回值】数据类型：图的邻接表数组adj 和图的顶点个数n, 队列操作过程：队列的创建、判空、入队、出队，队列需要指向队首和队尾的指针head 和 trail参数：邻接表表示的图g 和源点 s；返回值：返回数组和 d 构成的数据结构（2） 【数据设置】为了提高可读性，定义枚举类型Color ，包含颜色WHITE 、GRAY 和 BLACK 声明队列 Q，表示计算结果数组color （枚举类型）、 d （整型）和 pi （整型）；临时变量u 和 v （整型）（3） 【关键代码】顶点从0? n-1 编号。最短路径距离d 中 a 用整型最大值 INT_MAX 代替; 父结点数组；中空指

21、针NIL 用-1 表示；要输出路径还需要实现PRINT-PATH算法深度优先搜索 DFS 算法实现要点：（1） 【参数和返回值】数据类型：图的邻接表数组adj 和图的顶点个数n, 栈操作过程：栈的创建、判空、入栈、出栈，栈需要指向栈顶和栈底的指针top 和 bottom参数：邻接表表示的图g 和源点 s; 返回值：返回数组， d 和 f 构成的数据结构（2） 【数据设置】为了提高可读性，定义枚举类型Color , 包含颜色WHITE 、GRAY 和 BLACK 声明栈 S,表示计算结果数组 color （枚举类型）、 d （整型）、 f （整型）和 pi （整型）临时变量 u, v 和 s （

22、整型）（3）【关键代码】顶点从0? n-1 编号。父结点数组；中空指针NIL 用-1 表示；需要考虑如何实现第13 行： if v Adju a nd colorv = WHITE第十章泛型程序设计的主要思想将算法从特定的数据结构中抽象出来，成为通用的、可以作用于各种不同的数据结构。概念（ concept ）：用来界定具备一定功能的数据类型，如“支持< 运算符”的数据类型构成 Comparable这一概念；模型（ model ）：符合一个概念的数据类型称为该概念的模型，如int 型是 Comparable 概念的模型。STL 就是建立在模板函数和模板类基础之上的功能强大的库模板函数可以实

23、现一般化的常用算法（如统计、排序、查找等）模板类可以实现支持几乎所有类型的容器，用来实现常用的数据结构（如链表、栈、队列、平衡二叉树等）STL 头文件一览| 头文件内容头文件内春<iterator>迭代器<vector>向屋<utilrty>辅助功能<deque>双头駅列<memo ry>内存管理链表<algorrthm><set><functional>雷数对象<map>映射勺务重映射<numeric>数值运算<stack><queue>队列与优先队列欢迎