电工与电子技术电子商务电子课件数据与计算（第4版）Ch4 算法ppt

1、电子课件数据与计算（第4版）Ch4 算法Data and Computation 4Th,CS of ZJU, PHEIChapter 4 算法 AlgorithmCS, ZJU2019.8Overview算法的概念算法的三种结构算法的表示和发现常用算法算法的方法学数据表达和数据结构Data and Computation 4Th,CS of ZJU, PHEIKey chapter理解算法学习程序设计理解计算机解决问题的过程、方法理解计算机方法要求RaptorProject，and representation: Section 4.5Data and Computation 4Th,CS

2、of ZJU, PHEIAlgorithm高纳德（Donald EKnuth）图灵奖获得者程序设计和算法的先驱通过计算手段，“发现数据中隐藏的精妙规律”他认为：算法就是计算机科学的基础计算机是艺术品，不是科学Data and Computation 4Th,CS of ZJU, PHEI4.1 intruductionData and Computation 4Th,CS of ZJU, PHEI计算机的解决方法问题提出计算机可运行的程序软件问题解决程序用计算机语言对算法的描述求解问题的方法步骤算法程序就是算法的实现例子：欧几里德（Euclid）问题Data and Computation 4

3、Th,CS of ZJU, PHEI24和16的最大公约数是？Step 1：比较A和B，使A B；Step 2：A division B，得余数R（Remender）；Step 3：若C等于0，B就是最大公约数。结束。 否则将A B, BR，重复Step 2、Step3求解步骤=8求两个正整数A和B的最大公约数（GCD）计算公式其中mod是取余数思考一下？算法的定义算法是求解问题步骤的有序集合，它能够产生结果并在有限时间内结束Data and Computation 4Th,CS of ZJU, PHEI算法的特性（Donald EKnuth）确定性有穷性有效性可有零个或多个输入有一个或多个输

4、出算法的分类算法一般可分成两大类：数值运算算法非数值运算算法Data and Computation 4Th,CS of ZJU, PHEI算法的范式程序设计范式（Paradigm）不同的语言有不同的实现方案Edsger Wybe Dijkstra程序设计范式的提出者大O表示法算法的性能（1）存储空间（2）运行时间（主要）算法时间复杂度特殊的表示方法：大O表示法(Big O notation)例如n个数相加，需要执行的次数就是O(n)n个无序数中查找指定的数，运行时间也是O(n)不是精确的运算时间设计算法:“预测最糟糕的情况，做尽可能好的努力”Data and Computation 4Th,

5、CS of ZJU, PHEI几种典型的大O时间值O(1)，常数时间运算时间是一个常数，如计算函数值的算法时间O(log n)，对数时间如二分查找这类算法，准确表达应该是log2 n。O(n)，线性时间运行时间和参加运算的数据量n成线性关系。O(n2)，平方时间包括选择法在内的多种排序算法需要的时间。O(nlog n)快速排序的开销O(n!)，通常计算最短路径需要的时间Data and Computation 4Th,CS of ZJU, PHEI4.2 算法的三种结构所有的算法（程序）都由三种结构构成顺序结构，按照命令出现的先后顺序依次执行循环结构，按照设定的条件重复执行一组命令分支结构，根

6、据设定的条件来决定程序的执行方向基本形态表示了算法的逻辑过程，注重过程，so称为“面向过程”的程序设计Data and Computation 4Th,CS of ZJU, PHEI顺序结构A B分支结构Data and Computation 4Th,CS of ZJU, PHEIdo/while结构循环结构While结构 Data and Computation 4Th,CS of ZJU, PHEI4.3 算法的表示和发现算法的表示把算法以某种形式加以表达一个算法的表示可以有不同的方法常用方法自然语言传统的流程图结构流程图伪代码PAD图Data and Computation 4Th,C

7、S of ZJU, PHEI算法工具 Raptor自由软件(https:/)可执行的流程图赋值Assignment调用子程序Call输入输出选择循环Data and Computation 4Th,CS of ZJU, PHEIRaptorUsing Help数学函数+ - * / MOD Celling Floor Random关系运算 = /= != = =逻辑运算 AND OR NOT 子流程（Subchart），无返回值子程序（Subprocedure），有返回值提示信息 使用” ”Data and Computation 4Th,CS of ZJU, PHEI使用raptor实现欧几

8、里德GCD算法DemoData and Computation 4Th,CS of ZJU, PHEI求最大公约数的 C 程序#include stdio.hvoid main() int a,b,r,t; scanf(%d%d,&a,&b); if(ab) t=a;a=b;b=t; r=a % b; while(r) a=b; b=r; r=a%b; /* %号为求余 */ printf(最大公约数为%d,b);Data and Computation 4Th,CS of ZJU, PHEI流程图（Flowchart）Data and Computation 4Th,CS of ZJU, P

9、HEI欧几里德算法的流程图常用的流程图符号伪代码表示算法伪代码（Pseudo-code）表示算法的符号系统”专业人员使用自己喜爱的、或准备用于编程的计算机语言，加上英文描述混合而成注意伪代码中很多表达和程序语言相同或类似，但它不是计算机语言，不能被计算机执行Data and Computation 4Th,CS of ZJU, PHEI例：伪代码的欧几里德GCD算法Startinput positive integer a,bif a3, 3N-6条以上的边的图都不可能是平面的库托拉夫斯基证明：任何非平面图都包含如下子图中俄一个Data and Computation 4Th,CS of ZJ

10、U, PHEI平面图测试算法问题：将平面图的证明条件转化为算法大O值：O(n6)，100个点需要执行1亿次，1000点需要1018！霍普克洛夫特-陶尔扬算法划分子图测试图中的边数没有超过欧拉条件允许的数量划分子图：子图内的任意两个节点之间存在一条通路（含多边），且移走任何一个节点，图中节点还是联通的利用深度优先（ Depth First Search ）的算法，在图中找到一个“圈”-从一点出发经过几个节点又回到出发点移走该圈，将图分成一系列不连接的“桥”- 测试子图和桥是否一起组成平面图？如果圈位于平面，那么每一个桥要么在圈内，要么在其外.关键：一次深度搜索就可以完成技术Data and Co

11、mputation 4Th,CS of ZJU, PHEI霍普克洛夫特陶尔扬深度优先搜索（DFS）Example（首次论文“平面图测试的高效算法”长达20页）下图是平面图么，try？Data and Computation 4Th,CS of ZJU, PHEI 2 34 5 6163254右图：1632541 圈，是一个路径桥： 43 和 56 为“桥”-是平面图，大O值为O(n)About Algorithm，DFS 的启示算法的发现寻找算法也需要找到更好的算法一个更好的算法可能导致一个巨大的技术进步，例如求解问题-可计算性并非一下子就能够找到算法更别提找到最佳算法了Data and Co

12、mputation 4Th,CS of ZJU, PHEI4.4 算法举例理解常用的算法进而体会算法的发现、设计，是大多数学习计算机的人所采用的学习方法。4.4.1 基本算法-Self-learning累加(求和)累积求最大值和最小值求数的位数Data and Computation 4Th,CS of ZJU, PHEI4.4.2 迭代（Iteration）这是计算机算法中最常用的算法思路复杂问题化为简单问题由旧值推导新值的过程Data and Computation 4Th,CS of ZJU, PHEI算法思路是：迭代Iteration基于循环的算法, 例：判断一个整数是否为素数 算法思

13、路大O值Data and Computation 4Th,CS of ZJU, PHEI递归（Recursion）递归的必备知识：函数数学中凡此变数中函彼变数者,则此为彼之函数计算机中一段程序代码，可以被重复调用功能上和数学的函数类似函数调用将参数带入函数，返回一个结果Data and Computation 4Th,CS of ZJU, PHEI递归Recursion：是算法(程序)的自我调用例：求n的阶乘。Data and Computation 4Th,CS of ZJU, PHEI递归公式递归的伪代码Start Factorial ( n )/ 函数名，将n带入函数 if n=0 th

14、en return 1/递归出口 else return n* Factorial(n-1)/ 递归调用EndData and Computation 4Th,CS of ZJU, PHEI4.4.4 排序（Sort）迭代、递归的延续应用是将一组原始数据按照递增或递减的规律进行重新排列的算法应用广泛数值排序文本排序规则递增或递减，输出是原数据的重新排列Data and Computation 4Th,CS of ZJU, PHEI常用的排序(Sort)方法选择法排序把表中最小的数找到并放入第一个位置比较余下的数，找到次小的数放到第二个位置直到对所有数据全部扫描过冒泡法排序（习题4的T12）开始

15、比较相邻的两个数，将较小的向前移动，所有数比较完毕，得到最小的数在第一个位置剩下的数，持续这个过程，找到的次小的数排到列表的第二个位置依次类推，直到结束Data and Computation 4Th,CS of ZJU, PHEI选择法排序有一组6个数2，12，5，56，34，78从大到小排序Data and Computation 4Th,CS of ZJU, PHEI选择法排序的复杂度如图，6个元素排序不需要36次大约为15-16次n个数，扫描次数n-1次每次扫描元素依次减少，因此最多为1+2+n -1 n21/2，因此大O值应该为O(n2*1/2)大O表示法省略其中诸如1/2这样常数部

16、分,所以选择法的大O值：O(n2)And：大O值是最糟糕情况下的时间开销Data and Computation 4Th,CS of ZJU, PHEI查找算法从列表中找到某个数的的位置（即索引）两种基本的方法：顺序查找-未排序的数据，O(n) 折半查找-已经排序的数据, O(log n) 二分法，从列表的一半开始Data and Computation 4Th,CS of ZJU, PHEI顺序查找的伪代码Startread Array xinput key /输入要查找的数keyflag = false/flag为是否找到的标志i=0while( i=right)return “NoFou

17、nd”mid =( left+right)/2/ 计算中间位置的下标if (xmid = key )/ 找到了，返回 return midelse if(xmidkey) / 查找较大的那一半数组return halfSearch(x, key, mid-1, right)else / 查找较小的那一半数组return halfSerch(x, key, left, mid-1)endData and Computation 4Th,CS of ZJU, PHEI比较顺序查找-未排序的数据，O(n)折半查找-已经排序的数据, O(log n)例如，列表中有100,000个数，假设比较一次是1秒

18、顺序查找最坏的情况是需要100,000秒折半查找只需要log2100,00017秒顺序查找需要的时间是折半法的5882倍如果数据量为109，顺序查找的开销是二分法的3300万倍!因此大O表示法是算法的时间开销且随着数据量的增加而增加的-这才是大O表示法的意义所在Data and Computation 4Th,CS of ZJU, PHEI4.4.6 搜索图图也是一种数据类型图模拟一组连接由节点(node)和边(edge)组成Data and Computation 4Th,CS of ZJU, PHEIExample:Question 1: 从A点出发到B点，有路径吗Question 2:从

19、A点出发，到B点有最短的路径吗？有向图和无向图搜索方法：深度优先（depth first search，DFS）算法的方法学通常认为，算法没有方法学可资借鉴的某些方法贪心法分治法动态规划回溯法Data and Computation 4Th,CS of ZJU, PHEI枚举、蛮力法求解问题把所有可能的解都列出来，找到最后得到结果-穷尽可能这是很多基础性问题的算法没有方（办）法的方（办）法适用于规模较小、或者复杂度不高的问题。Example：解密，尝试密码的各种可能组合Data and Computation 4Th,CS of ZJU, PHEI贪心法经典例子找零钱问题你需要找给顾客N元零钱

20、，你手上有k 面值分别为X1,X2,.Xk的钱，且从大到小排列，为了用最少的零钱凑出N元钱思路先用最大面值的钱，再用次大面值的，一直到最后凑足N元钱。 这个算法就并不能求出最少需要的硬币数目So：贪心法只能求出一个较优解Data and Computation 4Th,CS of ZJU, PHEI埃及分数Fibonacci算法（1）用b除以a的商的整数部分加上1的值，作为埃及分数的某一个分母c；（2）将a乘以c减去b作为新的a。（3）将b乘以c作为新的b。（4）如果a大于1且能够整除b，则最后一个分母为b/a。（5）如果a等于1，则最后一个分母为b，否则转（1）继续。Try: 7/8=Dat

21、a and Computation 4Th,CS of ZJU, PHEI贪心法 贪心算法（Greedy Algorithm）从小的方案推广到大的解决方法。 “眼下能拿到就先拿到”求解最优问题一种通用的算法设计技术：可行性每一步选择必须满足问题的约束；局部最优它是当前可选择的方案中最优的；不可取消性选择一旦做出，在算法的其后步骤中不能被取消。缺点：可能不是最佳解Data and Computation 4Th,CS of ZJU, PHEIExample：背包问题一个贪婪的小偷，带着有个有限容积的背包，面对3个不同价值和体积的物品，他如何能够在背包中装入价值最高的商品组合而背包也能够放得下？D

22、ata and Computation 4Th,CS of ZJU, PHEI物品价值体积A，笔记本电脑2208B，艺术布罩台灯1206C，录音电话机1013解？最优么？只要它能够满足设计目标，它仍然具有价值Another Example著名的最短路径问题(TSP)也没有最优解如果一个旅行者需要经过n个城市，他的行程如何才能最短这需要用到数学中的组合学，要给出所有的可能路径，然后得到最短的那一个。如果有5个城市，线路是120条，如果城市增加1倍达到10个，那么需要计算的线路是10！超过300万条，是5个城市线路的2500倍。O(n!)! - 超大的O值贪心法从出发城市开始，每次选择下一个城市都

23、是没有去过、但距离最短的那个城市有意思：这个解的确有意义Data and Computation 4Th,CS of ZJU, PHEI分治法-分而治之何为好算法？算法的优劣都是和效率与速度相关与问题的规模相关分治法（Divide and Conquer）Divide：较大规模的问题分解为若干个较小规模的子问题，找出子问题的解Conquer: 各个子问题的解合并成整个问题的解基于递归包含两个以上的递归Data and Computation 4Th,CS of ZJU, PHEIExample：快速排序Quick Sort选择一个基数，例如第一个数。每个数与基数比较，分小、大两组对两组继续比较

24、分组.合并Data and Computation 4Th,CS of ZJU, PHEI12，56，5，34，2，11，785，2，111256，34，78521112563478Think about: Big O?Question: 哪一种情况下是最糟糕的？归并排序Merge Sorting将待排序的数分成数量基本相等的两组，重复分组排序，最后合并Data and Computation 4Th,CS of ZJU, PHEI12，56，5，34，2，11，7812 56 5 34 2 11 7812 56 5 34 2 11 7856 12 34 5 11 2 7856 34 12 5

25、 78 11 278 56 34 12 11 5 2第一次分组：第二次分组：第一次排序：第一次合并：第二次合并：比较快排与归并排序金块问题如何从一组数据中找出最大的和最小的有一个老板有一袋金块，被奖励优秀雇员金块：排名第一的雇员将得到袋中最重的金块排名第二的雇员将得到袋中最轻的金块如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块Data and Computation 4Th,CS of ZJU, PHEI动态规划背包问题容积为T的背包，如何能够在M个不同价值和体积的物品中，选择使包装下最大价值的物品N个D

26、ata and Computation 4Th,CS of ZJU, PHEI物品ABCDE体积34789价值45101113如背包体积为17，可装5件A=价值20，或D、E各1件价值24.问题的名称来源于如何选择最合适的物品放置于给定背包中。Data and Computation 4Th,CS of ZJU, PHEI动态规划（Dynamic Programming）美国数学家（Richard Bellman， 20世纪50 年代）建立、发展的一种解多阶段决策问题的优化方法思想一个较大问题被分解为若干个子问题，且子问题具有重叠（不是相互独立的，不适用分治法）可以将每个子问题的解存放到一个表

27、中，这样就可以通过查表解决问题另一个例子：斐波那契级数（Fibonacci Numbers）Data and Computation 4Th,CS of ZJU, PHEI回溯法回溯法也叫穷尽搜索法（Brute-Force Search），尝试分步地去解决一个问题。基本思想在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的、正确的解答的时候，将取消上一步甚至上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。通常使用递归实现Data and Computation 4Th,CS of ZJU, PHEI问题回溯法问题1：从N个自然数(1,2,n)中选出r个数的所有

28、组合。问题2：数的划分: 整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5; 1，5，1; 5，1，1;问有多少种不同的分法。问题3：经典问题， n皇后问题。在一个n n的棋盘上放置n个皇后，每行一个并使其不能互相攻击（同一列、同一行、同一斜行上的皇后都会自动攻击）。Data and Computation 4Th,CS of ZJU, PHEI数据表达和数据结构算法最终都需要通过适当的数据表达，以便能够被计算机所处理 - 抽象数据表达是对数据的符号化表示。数据结构的定义包括三方面内容：逻辑结构、存储结构和对数据的操作按照它的结构形式可以分为链、表、堆、队、树等Data and Computation 4Th,CS of ZJU, PHEI树型结构：数据元素存在一对多的关系数据结构数据元素是数据的基本单位,数据元素之间存在某种关联有三类基本的数据之间的结构Data and Computation 4Th,CS of ZJU, PHEI线性结构：数据元素存在一对一的关系图状结构：数据元素存在多对多的关系数据的逻辑关系抽象数类型是一组数学模型（对象）以及定义在该模型上的一组操作数据的逻辑关系如: 整数类型的对象是整数，对象的操作是、用程序设计语言实现相应的抽象数据类型对象逻辑结构的物理实