算法设计与分析第1章 算法引论ppt课件

1、算法设计与分析*河南工程学院第1 章 算法引论 主要内容 一、算法及其特性 二、算法的时间空间复杂度 三、算法分析(Algorithm Analysis) 1.分析算法时间复杂度的根本步骤 2.算法时间复杂度的有关概念 3.分析、求解算法复杂度的方法 四、迭代法 、递归算法设计与分析*河南工程学院1.1 算法1.2 算法描画1.3 算法分析的根底1.4 根本数据构造1.5 迭代法1.6 递归和消除递归算法设计与分析*河南工程学院 学习要求 掌握算法复杂度的根本概念 熟习算法复杂度分析的根本方法算法设计与分析*河南工程学院1.1 算法 一、算法(algorighm) 算法就是一组有穷的规那么，它

2、们规定理处理某一特定类型问题的一系列运算算法设计与分析*河南工程学院 Gcd (int a, int b) 1 if ab 2 then swap (a,b) 3 na%b 4 while n0 5 do ab; 6 bn; 7 a%b; 8 return b;算法设计与分析*河南工程学院1.1 算法 二、算法的特点 1. 有穷性 2. 确定性 3. 输入 4. 输出 5. 能行性算法设计与分析*河南工程学院 程序是算法用某种程序设计言语的详细实现。 程序可以不满足算法的性质(1)。 例如操作系统，是一个在无限循环中执行的程序，因此不是一个算法。 操作系统的各种义务可看成是单独的问题，每一个问

3、题由操作系统中的一个子程序经过特定的算法来实现。该子程序得到输出结果后便终止。算法设计与分析*河南工程学院1.2 算法的描画 自然言语 流程图 PAD图 盒图 伪代码 计算机程序设计言语算法设计与分析*河南工程学院 1.2.1 算法描画商定 根本数据类型: vartype var; 赋值语句： 逻辑运算：and, or, not 关系运算, =,=,=,等 数组描画：vartype arraynamen 三种根本的控制构造 1.顺序构造 2.选择构造 3.循环构造 动态空间恳求函数 malloc(size) 模块描画 其他细节阐明 算法设计与分析*河南工程学院 1.2.1 一个简单问题的求解过

4、程 1. 问题分析：对问题进展准确的了解和描 述从而确认问题以及问题的根本运算，并明确求解问题 2. 算法分析：根据确定的问题，找出问题的处理方法或数学模型，对处置功能求解，并用算法言语进展描画 3.算法设计：对确定的算法，选择数据构造对分析得到的算法进展设计 4.算法实现：利用程序设计和软件开发方法经过程序编辑、编译、运转于调试实现算法，对问题进展计算机求解。算法设计与分析*河南工程学院1.3 算法分析的根底 1.3.1 算法分析的评价体系 算法分析主要分析算法在运转时占用的计算机资源是多少，既算法运转时的时间和空间效率 好的算法在完胜利能的前提先占用空间少且执行时间短算法设计与分析*河南工

5、程学院 对算法的分析和评价，普通应思索正确性、可维护性、时间效率及占用存储空间等诸多要素。其中评价算法的三条主要规范是： 1、算法实现所耗费的时间 2、算法实现所耗费的存储空间 3、算法应易于了解、易于编码、易于调试。算法设计与分析*河南工程学院 算法复杂性 = 算法所需求的计算机资源 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模输入大小。算法设计与分析*河南工程学院 1.3.2 算法的时间复杂度 一、影响算法执行时间的要素 1. 问题中数据存储的数据构造 2.算法中采用的数学模型 3.算法设计的战略 4.问题规模 5.实现算法的程序执行言语 6.编译算法产生的机

6、器代码的质量 7.计算机执行指令的速度算法设计与分析*河南工程学院 分析算法的时间复杂度常用的两种方法： 事后测试(Posterior Test)方法 事前分析(Priori Analysis)方法算法设计与分析*河南工程学院 二、 时间复杂度 定义1-1 在问题规模为n的算法中，假设存在两个正常数C和n0，对恣意nn0,都有 |g(n)|C|f(n)| 那么记作|g(n)|=O(f(n)。其中，O为数量级，即阶数。因此，但说一个算法具有O(g(n)的计算时间时，指的假设此算法用n值不变的同一类数据在某台机器上运转时，所用时间总是小于|f(n)|的常数倍。所以f(n)是计算时间g(n)的一个上

7、界函数，g(n)的数量级为f(n).算法设计与分析*河南工程学院 定义1-2 算法中根本操作反复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作 T(n)=O(f(n) 随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率一样，称作算法的渐进时间复杂度，简称时间复杂度。算法设计与分析*河南工程学院 三、时间复杂度估算 假设在程序中有语句xx+y, 这条语句的时间总量=该语句执行的次数每执行一次该语句所需求的时间； 例1 for 1to n do for 1j to n do xx+1; 语句的最大频度为n2,所以其时间复杂度可表示为O(n2).算法设计与分析*河南工程学院

8、算法中对所研讨的问题最重要的操作作为原操作，已原操作在算法中反复执行的次数作为算法运转时间的衡量准那么。 例2 a b c xx+y for 1i to n for 1i to n do xx+y do for 1j to n doxx+y ; 1 n n2 O(1) O(n) O(n2)算法设计与分析*河南工程学院 定理1-1 假设A(n)=amnm+ +a1n+a0 是一个m次多项式，那么A(n)=O(nm) 证明：取n0=1,当nn0时有 |A(n)|am|nm+ |am-1|nm-1+|a1|n+|a0| (|am|+ |am-1|1/n+|a0|1/nm)nm (|am|+ |a m

9、-1|+|a0|)nm 选取 C=|am|+|am-1|+|a0| 定理阐明，变量n的阶数为m的多项式与其最高价nm同阶。因此计算时间为m阶的多项式的算法，其时间都可用O(nm)来表示。算法设计与分析*河南工程学院 定义1-3 假设存在两个正常数C和n0，对恣意nn0都有 |g(n)| C|f(n)| 那么记为g(n)=(f(n)。定义阐明f(n)是g(n)的下界函数。 定义1-4 假设存在正常数C1,C2和n0，对于一切的nn0，有 C1|f(n)| g(n) C2|f(n)| 那么记为g(n)=(f(n).算法设计与分析*河南工程学院 一个算法g(n)=(f(n)阐明该算法在最好和最坏情况

10、下的计算时间就某一常数而言是一样的。算法设计与分析*河南工程学院 比较两个函数的阶数的方法 假设 lim f(n)/g(n)=L 有是以下三种情况 1. 假设L=a, a 是有限正常数，那么g(n)=(f(n). 2. 假设L=0，那么f(n)的阶数比g(n)底 3. 假设L= ，那么f(n)的阶数比g(n)高算法设计与分析*河南工程学院算法分析中常见的复杂性函数算法分析中常见的复杂性函数算法设计与分析*河南工程学院小规模数据小规模数据算法设计与分析*河南工程学院中等规模数据中等规模数据算法设计与分析*河南工程学院 四、时间复杂度的最好情况和最坏情况算法设计与分析*河南工程学院 1.3.3 算

11、法的空间复杂度 算法的空间复杂度是指算法在执行过程中所占辅助存储空间的大小，用S(n)表示。算法的空间复杂度S(n)可表示为 S(n)=O(f(n)算法设计与分析*河南工程学院 1.3.4 NP-完全问题 可在多项式时间内用确定求精的断定问题的集合称为P类问题。而一切在多项式时间内用不确定算法求解的判别问题的集合称为NP-问题算法设计与分析*河南工程学院 确定算法是不确定算法的一种特例，任何一个P类问题都属于NP类问题算法设计与分析*河南工程学院1.4 根本数据构造 1.4.1 栈和队列 顺序栈的数据构造 typedef struct 1 SElemType *base; 2 SElemTyp

12、e *top; 3 int stacksize; 4 sqStack.算法设计与分析*河南工程学院Push (sqStack, &SElmType e)if S.top-S.base=S.stacksize then if S.base=NULL then exit; S.topS.base+S.stacksize; S.stacksizeS.stacksize+stackincrement*S.tope;S.topS.top+1;算法设计与分析*河南工程学院 Pop (sqStack &S, SElmType &e) 1 if S.top=S.base 2 then return ERROR

13、 3 S.topS.top-1; 4 e*S.top 5 return算法设计与分析*河南工程学院 链队列的数据构造 typedef struct Qnode 1 QElemType data; 2 struct Qnode *next; 3 Qnode; typedef struct 1 Qnode *front; 2 Qnode *rear; 3 LinkQueue;算法设计与分析*河南工程学院 EnQueue(LinkQueue &Q, QElemType e 1 p(Qnode *) malloc (sizeof(Qnode); 2 if NULL=p 3 then exit(OVER

14、LOW) 4 p.datae 5 p.nextNULL 6 Q.rear.nextp; 7 Q.rearp; 8 return OK;算法设计与分析*河南工程学院 1.4.2 树 定义1-5 树是由一个或多个节点组成的有限集合T，节点满足如下关系： 1由一个特定的节点称为数的根节点 2其他节点被分成m(m=0)个互不相交的集合T1,T2, ,Tm，其中每个集合本身又是一颗树，被称为根节点的子树。算法设计与分析*河南工程学院 树的根本术语 1. 孩子、双亲、兄弟 2 节点的度 3 叶节点、分支节点 4 节点的层数 5 树的深度 6 二叉树、满二叉树、完全二叉数算法设计与分析*河南工程学院 1.4

15、.3图 图G是由称之为定点(Vertices)V和边(Edges)E的两个集合所组成，记作G=,V是一个有限非空的定点集合，这些定点通常记为v1,v2, ,v n。E那么是定点对偶的集合。E中的每一对偶就是G的一条边。算法设计与分析*河南工程学院 有向图：假设图中的对偶是有序的，那么称图是有向图，否那么是无向图。有向图用尖括号来表示，无向图用圆括号来表示(v1,v2). 权：图的边或弧有时与一些数值相关，称作权Weight)，带权的图称为网络(Network).算法设计与分析*河南工程学院1.5 迭代法 迭代法是一种不断用变量的当前值推出新值的处理问题的方法。利用迭代战略求解问题，分三步进展

16、1.确定迭代模型 2.建立迭代关系式 3.迭代过程控制算法设计与分析*河南工程学院 1.5.1 递推法 递推法是迭代法的最简单方式。简单的递推方式，是从小规模的问题推出解出大规模问题的方法，也称为“正推算法设计与分析*河南工程学院 1.5.2 倒推法 倒推法是指对某些特殊问题所采用的违反常规的，从后向前推解问题的方法算法设计与分析*河南工程学院 1.5.3 迭代法解方程 迭代法解方程的本质是按照以下步骤构造一个序列x0,x1,x2,xn, 来逐渐逼近方程f(x)=0的解 1 选取适当的初值x0； 2 确定迭代格式，即建立迭代关系，将方程f(x)=0 改写为x=(x)的等价方式。算法设计与分析*

17、河南工程学院算法设计与分析*河南工程学院1.6 递归和消除递归 1.6.1 递归 递归算法中一个模块函数、过程除了可调用其他模块函数、过程外，还可以直接或间接地调用本身。 递归是一种比迭代更强、更好的构造。它把一个复杂的大问题层层转化为一个原问题类似的简单的小问题，然后逐渐求解小问题，最后经过回溯法得到原问题的解。算法设计与分析*河南工程学院 递归算法的三步骤1. 分析问题、寻觅递归 2. 设置边境、控制递归 3.设计函数、确定参数算法设计与分析*河南工程学院例例 阶乘函数阶乘函数 阶乘函数可递归地定义为：阶乘函数可递归地定义为：00)!1(1!nnnnn边境条件边境条件递归方程递归方程边境条

18、件与递归方程是递归函数的二个要素，递归函数只需具备了这两个要素，才干在有限次计算后得出结果。算法设计与分析*河南工程学院例例 Fibonacci Fibonacci数列数列无穷数列无穷数列1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434，5555，称为，称为FibonacciFibonacci数列。它可以递归地定义为：数列。它可以递归地定义为：边境条件边境条件递归方程递归方程110)2() 1(11)(nnnnFnFnF第n个Fibonacci数可递归地计算如下：int fibonacci(int n) if (n 0 2 then Hanoi(n-1,a,c,b); 3 print(“Move disc, n. “from pile, a, “to b); 4 hanoi(n-1,c,b,a)算法设计与分析*河南工程学院优点：构造明晰，可读性强，而且容易用优点：构造明晰，可读性强，而且容易用数学归纳法来证明算法的正确