最新算法及其基础教学讲义PPT.ppt

《最新算法及其基础教学讲义PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法及其基础本章的要点与难点要点:理解算法的概念。程序与算法的区别和联系；理解算法设计的一般过程；掌握用C++/JAVA语言以及伪代码描述算法的方法；掌握算法的计算复杂性概念及分析。难点:算法的计算复杂性（主要指时间复杂性）分析。1.1引子–排序问题排序问题描述：输入：数字序列X=输出：一个排列X‘=，数字序列X和排列X‘之间为满射或一一映射（即元素一一对应），并且有a‘1≤a‘2≤…≤a‘n（元素间非减序）。例如：输入：8,2,4,9,3,6

2、输出：2,3,4,6,8,9排序方法：冒泡、插入、归并、二叉树、桶排序等。稳定的；选择、Shell、堆、快速、组合排序等，不稳定的。1.1引子–插入排序运行时间分析：最坏情况：T(n)=O(n2)。，算术级数。已非升序排序；平均情况：T(n)=O(n2)。，算术级数；最好情况：T(n)=O(n)。，已升序排序。1.1引子–归并排序原理：基于分而治之思想，递归地把待排序序列分解为若干子序列并进行排序，再把已排序的子序列合并为整体有序序列，最终实现全序列的有序。伪代码：MERGE-SORT(A,low

3、,high)//A[1..n]iflow

4、是若干条指令的有穷序列。算法的特性：输入（0个或多个）、输出（至少1个）、确定性（无歧义）、有限性、可行性。描述方式：自然语言、图形、程序设计语言、伪代码本书采用了面向对象程序设计语言C++，讲授时采用伪代码。算法与程序的区别？1.2算法的基本概念–算法程序(Program)程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的性质(4)。例如：操作系统是一个在无限循环中执行的程序，因而其不是一个算法；操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来

5、实现。1.2算法的基本概念–程序会场安排问题、单源最短路径、哈夫曼编码、最小生成树排序与查找、循环赛日程表最长公共子序列、矩阵连乘、凸多边形最优三角剖分、加工顺序等N后、最大团、图的m着色0-1背包、TSP、布线问题等等1.2算法的基本概念–经典问题1.2算法的基本概念–拼图游戏在n×n格的棋盘上放置彼此不受攻击的n个皇后：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子；n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。12345

6、67812345678QQQQQQQQ1.2算法的基本概念–N后问题1.2算法的基本概念–0-1背包问题起点XXXXXXXXXXXXXXXXXXXX终点XXXXX1.2算法的基本概念–布线问题1.3算法设计的一般过程算法复杂性（亦称算法复杂度）为算法运行时所需计算机资源的度量：时间复杂性（影响因素包括问题规模n、输入序列I、算法本身A）：T(n,I,A)T(n)空间复杂性（影响因素包括输入输出数据IO、辅助变量V、算法本身A）：S(IO,V,A)S(V)很显然：算法所需资源越多，算法的复杂性就

7、越高；算法所需资源越少，算法的复杂性就越低。1.4算法分析–算法复杂性算法分析：对算法的时间复杂性和空间复杂性进行分析，这里主要还是指对算法的时间复杂性的分析。方法：事后统计和事前分析算法分析的意义：算法设计：复杂性尽可能的低；算法选用：选择复杂性最低的算法；算法改进：算法分析有助于算法的改进。1.4算法分析影响算法运行时间的因素（除算法本身外）：机器；采用语言及编译程序；编程能力等。算法分析无需具体时间（精确或近似）：针对同一问题不同算法的比较，相对而非绝对；应该独立于机器及实现语言；无论科技如

8、何发展，其运行时间的测度应始终成立；关心的是大的问题规模时的运行情况。渐近复杂性1.4算法分析–算法渐近复杂性态：设算法的运行时间为T(n)，如果存在T*(n)，使得就称T*(n)为算法的渐近性态或渐近时间复杂性。1.4算法分析–算法渐近复杂性态?假设算法A的运行时间表达式为T1(n)：T1(n)=30n4+20n3+40n2+46n+100T*1(n)≈n4（阶）假设算法B的运行时间表达式为T2(n)：T2(n)=1000n3+50n2+78n+10T*2(n)≈n3（阶）1.