算法分析与设计

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

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

3、1#define MAX20n1n1n1n11 nn 1 n*iOjOiOiONO(i) 0( i) O(n(n2 1) O(N0i1O赋值，比较，算术运算，逻辑运算，读写单个变量(常量)只需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

4、do s (repeat s until c)语句时间=(Tc+Ts) *循环次数.7) .用goto从循环体内跳到循环体末或循环后面的语句时，不需额外时间8) .过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则17进行分析；对递归调用，可建 立关于T (n)的递归方程，求解该方程得到T (n).插入排序算法的实现要点：(1)【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式(即逻辑结 构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。（2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。每个变

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

6、Apq和Aq+1r，可以表示为区间p,q,q,r指针（或迭代器）p， q，r ： p指向第一个子序列的首元素，q指向第二个子序列首元素，r指向第二个子序列末尾元素之后，单个 元素数据长度及比较函数指针。返回值：无（2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。每个变量都要考虑它的 数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初 始值。（3）【关键代码】要考虑直接转换还是需要建立相应的独立函数。对于赋值和下标通常可以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建

7、立 专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。序列的划分算法的实现要点：（1 ）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结 构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。参数：A是数组或序列p,r分别是整数或者迭代器返回值：分界点位置的整数或者迭代器（2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。每个变量都要考虑它的 数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初 始值。（3）【关键代码】要考虑直接转换还是需要建

8、立相应的独立函数。对于赋值和下标通常可以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立 专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。第二章直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。分治法的 设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治策略在每一层递归包括3个步骤：分解将问题分解成若干个子问题。治理递归地解决各子问题。不过若子问题的规模足够小，就以直接的方式(不再递归)解决子问题。合并将子问题的解合并成原问题的一个解。divide-a

9、nd-conquer(P)if (I P I <= nO) adhoc(P); .,Pk ; .,yk); /将各子问题的解合并为原问题的解)分治法的复杂性分析：一个分治法将规模为n的问题分成k个规模为n/ m的子问题去解。设分解阀值O(1)nkT(n/m)f(n) 1通过迭代法求得方程n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将 k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有:log m k m j jT(n)nkf (n/m)的解：j。递归小结：优点：结

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

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

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

13、解，动态规划将分解后的 子问题理解为相互间有联系，有重叠的部分。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 （对应矩阵D和口）；循环控制变量i，j，k （

14、整数）（3）【关键代码】顶点从。n-1编号。邻接矩阵D中8用浮点型最大值代替；父结点矩阵口中空指针NIL用表示；要输出路径还需要实现PRINT-ALL-PAIRS-SHORTEST-PAT W H法S第四章：贪心算法：依赖于当前已经做出的所有选择，采用自顶向下（每一步根据策略得到当前一个最优解，保证 每一步都是选择当前最优的）的解决方法。贪婪算法设计的3个步骤：（1 ）分析问题的最优子结构（2）分析问题的贪婪选择性质（3）根据最优子结构和贪婪性质自顶向下计算最优解。Huffman算法实现要点：（1）【参数和返回值】参数：字符集C及频数数组及个数；返回值：返回二叉树（2）【数据设置】需要最小优先

15、队列Q ；循环控制变量i （整数）（3）【关键代码】需要先实现二叉树的数据结构单源最短路径算法实现要点（与prim算法类似）：（1）【参数和返回值】参数：图形矩阵W （浮点型）及顶点数n （整型）及源点s （整型）返回值：返回key和pi的数据结构（2）【数据设置】需要浮点型数组d和整型数组pi，需要最小优先队列Q ；需要顶点变量u和v （整数）（3）【关键代码】需要先实现动态优先队列广度优先搜索BFS算法实现要点：（1）【参数和返回值】数据类型：图的邻接表数组adj和图的顶点个数n，队列操作过程：队列的创建、判空、人队、出队，队列需要指向队首和队尾的指针head和trail参数：邻接表表示的

16、图g和源点s；返回值：返回数组和d构成的数据结构（2）【数据设置】为了提高可读性，定义枚举类型Color，包含颜色WHITE、GRAY和BLACK。声明 队列Q，表示计算结果数组color （枚举类型）、d （整型）和pi （整型）；临时变量u和v （整型）（3）【关键代码】顶点从。n-1编号。最短路径距离d中用整型最大值INT_MAX代替；父结点数组；中空指针NIL用表示；要输出路径还需要实现PRINT-PATHS算法深度优先搜索DFS算法实现要点：（1）【参数和返回值】数据类型：图的邻接表数组adj和图的顶点个数n，栈操作过程：栈的创建、判空、入栈、出栈，栈需要指向栈顶和栈底的指针top和

17、bottom参数：邻接表表示的图g和源点s ;返回 值：返回数组，d和f构成的数据结构（2）【数据设置】为了提高可读性，定义枚举类型Color，包含颜色WHITE、GRAY和BLACK。声明 栈S，表示计算结果数组color （枚举类型）、d （整型）、f （整型）和pi （整型）临时变量u，v和 s （整型）（3）【关键代码】顶点从。n-1编号。父结点数组；中空指针NIL用1表示；需要考虑如何实现第13 行：if v Adju and colorv = WHITE第十章泛型程序设计的主要思想将算法从特定的数据结构中抽象出 来，成为通用的、可以作用于各种不同的数据结构。概念（concept ）

18、：用来界定具备一定功能的数据类型，如"支持V'运算符”的数据类型构成Comparable这一概念；模型（model ）：符合一个概念的数据类型称为该概念的模型，如 int型是Comparable概念 的模型。STL就是建立在模板函数和模板类基础之上的功能强大的库模板函数可以实现一般化的常用算法（如统计、排序、查找等)模板类可以实现支持几乎所有类型的容器，用来实现常用的数据结构(如链表、栈、队列、 平衡二叉树等)容器(Container )容器是存放其他对象的对象，是容纳、包含一组元素的对象一种为顺序容器(sequence contsainer )，另一种为关联容器(associative container ) 迭代器(Iterator )提供了顺 序访问容器中每个