算法分析与设计_论文-毕业文章.pdf

第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。算法的三个要素 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 AMAXMAX,int BMAXMAX,int CMAXMAX)int i,j;for(i=0;in;i+)for(j=0;jn;j+)Cij=Aij+Bij;该算法中的基本运算是两重循环中最深层的语句 Cij=Aij+Bij，分析它的频度，即：T(n)=102101010*11ninininjnnnnn=O(n2)分析以下算法的时间复杂度。void func(int n)int i=0,s=0;while(sn)i+;s=s+i;欢迎下载 2 对于 while 循环语句，设执行的次数为 m，i 从 0 开始递增 1，直到 m 为止，有：s=0+1+2+(m-1)=m(m-1)/2，并满足 s=m(m-1)/2n，则有 m n。T(n)=O(n)所以，该算法的时间复杂度为 O(n)。有如下算法：void fun(int a,int n,int k)/数组 a 共有 n 个元素 int i;if(k=n-1)for(i=0;in;i+)/n 次 printf(%dn,ai);else for(i=k;in;i+)/n-k 次 ai=ai+i*i;fun(a,n,k+1);调用上述算法的语句为 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()1O(1O(11iijij）外循环共需)O(N)21O()O()O(21N1)(NNiiNii 渐进分析 时间复杂性渐进阶分析的规则：(最坏情况)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).依次执行一个正确的算法中的各操作步骤最终将得到该问题的解正确的输出数据算法的三个要素数据运算序列中作为运算对象和结果的数据运算运算序列中的各种运算赋值算术和逻辑运算控制和转移运算序列中的控制和转移算法分行算法串行计算机上执行的算法并行算法并行计算机上执行的算法算法的五个重要的特性有穷性在有穷步之后结束确定性无二义性可行性可通过基本运算有限次执行来实现有输入表示存在数据处理有输出伪代码程序设计语言也称为语言的语法特点使用一些固定关键词的语法结构表达了结构化构造数据描述模块的特征以自然语言的自由语法描述了处理过程数据声明应该既包括简单的也包括复杂的数据结构使用支持各种模式的接口描述的子程序定义或者调用技 欢迎下载 3 插入排序算法的实现要点：（1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。（2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。（3）【关键代码】要考虑直接转换还是需要建立相应的独立函数。对于赋值和下标通常可以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。归并排序算法的实现要点：（1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。参数：序列 Apr的子序列 Apq和 Aq+1r，可以表示为区间p,q,q,r 指针（或迭代器）p，q，r：p 指向第一个子序列的首元素，q 指向第二个子序列首元素，r指向第二个子序列末尾元素之后，单个元素数据长度及比较函数指针。返回值：无（2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。（3）【关键代码】要考虑直接转换还是需要建立相应的独立函数。对于赋值和下标通常可以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。序列的划分算法的实现要点：（1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。参数：A 是数组或序列 p,r 分别是整数或者迭代器 返回值：分界点位置的整数或者迭代器（2）【数据设置】变量定义与初值设定。要考虑访问的所有数据，包括变量和常量。每个变量都要考虑它的数据类型、存储结构、访问控制（局部变量、全局变量、静态变量、公共属性、保护属性、私有属性等）和初始值。（3）【关键代码】要考虑直接转换还是需要建立相应的独立函数。对于赋值和下标通常可以直接转换。一些操作，比如数据输入、创建、求长度、查找、排序、插入、删除、显示、修改等操作，通常需要通过建立专门的独立函数来实现，也可以通过系统提供的命令或函数来实现。第二章 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。依次执行一个正确的算法中的各操作步骤最终将得到该问题的解正确的输出数据算法的三个要素数据运算序列中作为运算对象和结果的数据运算运算序列中的各种运算赋值算术和逻辑运算控制和转移运算序列中的控制和转移算法分行算法串行计算机上执行的算法并行算法并行计算机上执行的算法算法的五个重要的特性有穷性在有穷步之后结束确定性无二义性可行性可通过基本运算有限次执行来实现有输入表示存在数据处理有输出伪代码程序设计语言也称为语言的语法特点使用一些固定关键词的语法结构表达了结构化构造数据描述模块的特征以自然语言的自由语法描述了处理过程数据声明应该既包括简单的也包括复杂的数据结构使用支持各种模式的接口描述的子程序定义或者调用技 欢迎下载 4 分治策略在每一层递归包括 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 个规模为 nm 的子问题去解。设分解阀值 n0=1，且adhoc 解规模为 1 的问题耗费 1 个单位时间。再设将原问题分解为 k 个子问题以及用 merge将 k 个子问题的解合并为原问题的解需用 f(n)个单位时间。用 T(n)表示该分治法解规模为|P|=n 的问题所需的计算时间，则有：11)()/()1()(nnnfmnkTOnT通过迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT 递归小结：优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。解决方法：在递归算法中消除递归调用，使其转化为非递归算法。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=am)return m;if(x am)r=m-1;else l=m+1;return-1;依次执行一个正确的算法中的各操作步骤最终将得到该问题的解正确的输出数据算法的三个要素数据运算序列中作为运算对象和结果的数据运算运算序列中的各种运算赋值算术和逻辑运算控制和转移运算序列中的控制和转移算法分行算法串行计算机上执行的算法并行算法并行计算机上执行的算法算法的五个重要的特性有穷性在有穷步之后结束确定性无二义性可行性可通过基本运算有限次执行来实现有输入表示存在数据处理有输出伪代码程序设计语言也称为语言的语法特点使用一些固定关键词的语法结构表达了结构化构造数据描述模块的特征以自然语言的自由语法描述了处理过程数据声明应该既包括简单的也包括复杂的数据结构使用支持各种模式的接口描述的子程序定义或者调用技 欢迎下载 5 算法复杂度分析：每执行一次算法的 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）【关键代码】顶点从 0n-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（整数）依次执行一个正确的算法中的各操作步骤最终将得到该问题的解正确的输出数据算法的三个要素数据运算序列中作为运算对象和结果的数据运算运算序列中的各种运算赋值算术和逻辑运算控制和转移运算序列中的控制和转移算法分行算法串行计算机上执行的算法并行算法并行计算机上执行的算法算法的五个重要的特性有穷性在有穷步之后结束确定性无二义性可行性可通过基本运算有限次执行来实现有输入表示存在数据处理有输出伪代码程序设计语言也称为语言的语法特点使用一些固定关键词的语法结构表达了结构化构造数据描述模块的特征以自然语言的自由语法描述了处理过程数据声明应该既包括简单的也包括复杂的数据结构使用支持各种模式的接口描述的子程序定义或者调用技 欢迎下载 6（3）【关键代码】需要先实现动态优先队列 第六章 广度优先搜索 BFS算法实现要点：（1）【参数和返回值】数据类型：图的邻接表数组 adj 和图的顶点个数 n，队列 操作过程：队列的创建、判空、入队、出队，队列需要指向队首和队尾的指针 head 和 trail 参数：邻接表表示的图 g 和源点 s；返回值：返回数组和 d 构成的数据结构（2）【数据设置】为了提高可读性，定义枚举类型 Color，包含颜色 WHITE、GRAY和 BLACK。声明队列 Q，表示计算结果数组 color（枚举类型）、d（整型）和 pi（整型）；临时变量 u和 v（整型）（3）【关键代码】顶点从 0n-1编号。最短路径距离 d 中用整型最大值 INT_MAX代替；父结点数组；中空指针 NIL用-1表示；要输出路径还需要实现 PRINT-PATHS 算法 深度优先搜索 DFS算法实现要点：（1）【参数和返回值】数据类型：图的邻接表数组 adj 和图的顶点个数 n，栈 操作过程：栈的创建、判空、入栈、出栈，栈需要指向栈顶和栈底的指针 top 和 bottom 参数：邻接表表示的图 g 和源点 s；返回值：返回数组，d 和 f 构成的数据结构（2）【数据设置】为了提高可读性，定义枚举类型 Color，包含颜色 WHITE、GRAY和 BLACK。声明栈 S，表示计算结果数组 color（枚举类型）、d（整型）、f（整型）和 pi（整型）临时变量 u，v 和 s（整型）（3）【关键代码】顶点从 0n-1编号。父结点数组；中空指针 NIL用-1表示；需要考虑如何实现第 13 行：if v Adju and colorv=WHITE 第十章 泛型程序设计的主要思想 将算法从特定的数据结构中抽象出来，成为通用的、可以作用于各种不同的数据结构。概念（concept）：用来界定具备一定功能的数据类型，如“支持运算符”的数据类型构成 Comparable 这一概念；模型（model）：符合一个概念的数据类型称为该概念的模型，如 int 型是 Comparable 概念的模型。STL就是建立在模板函数和模板类基础之上的功能强大的库 模板函数可以实现一般化的常用算法（如统计、排序、查找等）模板类可以实现支持几乎所有类型的容器，用来实现常用的数据结构（如链表、栈、队列、平衡二叉树等）容器（Container）容器是存放其他对象的对象，是容纳、包含一组元素的对象 一种为顺序容器（sequence contsainer），另一种为关联容器（associative container）依次执行一个正确的算法中的各操作步骤最终将得到该问题的解正确的输出数据算法的三个要素数据运算序列中作为运算对象和结果的数据运算运算序列中的各种运算赋值算术和逻辑运算控制和转移运算序列中的控制和转移算法分行算法串行计算机上执行的算法并行算法并行计算机上执行的算法算法的五个重要的特性有穷性在有穷步之后结束确定性无二义性可行性可通过基本运算有限次执行来实现有输入表示存在数据处理有输出伪代码程序设计语言也称为语言的语法特点使用一些固定关键词的语法结构表达了结构化构造数据描述模块的特征以自然语言的自由语法描述了处理过程数据声明应该既包括简单的也包括复杂的数据结构使用支持各种模式的接口描述的子程序定义或者调用技 欢迎下载 7 迭代器（Iterator）提供了顺序访问容器中每个元素的方法。迭代器相当于指针，它提供了一种一般化的方法使得 C+程序能够访问不同数据类型的顺序或者关联容器中的每一个元素，我们可以称它为“泛型指针”。五种迭代器类型，前向迭代器（forward iterator），双向迭代器(bidirectional iterator)，输入迭代器(input iterator)，输出迭代器(output iterator)，随机访问迭代器(random access iterator)算法（Algorithm）不可变序列算法（non-modifying sequence algorithms）、可变序列算法(mutating sequence algorithms)、排序及相关算法(sorting and related algorithms)和算术算法（numeric algorithms）。仿函数（Function object）函数对象是 STL 提供的四种组件中的一种，它是定义了操作符operator()的对象，是泛化的函数。适配器（Adaptor）一种接口类，可以认为是标准组件的改装。通过修改其它类的接口，使适配器满足一定需求。可分为容器适配器、迭代器适配器和函数对象适配器三种。分配器（allocator）STL提供的一种内存管理类模块。每种 STL容器都是用了一种分配器类，用来封装程序所用的内存分配模式的信息。依次执行一个正确的算法中的各操作步骤最终将得到该问题的解正确的输出数据算法的三个要素数据运算序列中作为运算对象和结果的数据运算运算序列中的各种运算赋值算术和逻辑运算控制和转移运算序列中的控制和转移算法分行算法串行计算机上执行的算法并行算法并行计算机上执行的算法算法的五个重要的特性有穷性在有穷步之后结束确定性无二义性可行性可通过基本运算有限次执行来实现有输入表示存在数据处理有输出伪代码程序设计语言也称为语言的语法特点使用一些固定关键词的语法结构表达了结构化构造数据描述模块的特征以自然语言的自由语法描述了处理过程数据声明应该既包括简单的也包括复杂的数据结构使用支持各种模式的接口描述的子程序定义或者调用技