算法及其基础.ppt

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

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

2、序）。例如：输入：8,2,4,9,3,6输出：2,3,4,6,8,9排序方法：冒泡、插入、归并、二叉树、桶排序等。稳定的；选择、Shell、堆、快速、组合排序等，不稳定的。1.1引子–插入排序原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。伪代码：INSERTION-SORT(A,n)//A[1..n]forj=2tondokey=A[j]i=j-1whilei>0andA[i]>keydoA[i+1]=A[i]i=i-1A[i+1]=key1.1引子–插入排序示例：1.1引子–插入排序证明–基于循环不变

3、式(LoopInvariant)：循环不变式：在每次循环迭代之前，子数组A[1..j-1]已包含了最初位于A[1..j-1]、但已排好序的各个元素。初始化：第一轮迭代之前（即j=2），子数组A[1..j-1]（即A[1]）显然保持了循环不变式；保持：假设第j次迭代之前循环不变式为真。该算法的第j次操作只是将A[j]与已有序的A[1..j-1]中的元素进行比较，找到合适位置并插入。j+1次迭代之前，很显然A[1..(j+1)-1]也保持了循环不变式；终止：j=n+1时，显然A[1..(n+1)-1]（即A[1..n]）已包含了最初位于A[1..n

4、]、且已排好序的各个元素。1.1引子–插入排序运行时间分析：最坏情况：T(n)=O(n2)。，算术级数。已非升序排序；平均情况：T(n)=O(n2)。，算术级数；最好情况：T(n)=O(n)。，已升序排序。1.1引子–归并排序原理：基于分而治之思想，递归地把待排序序列分解为若干子序列并进行排序，再把已排序的子序列合并为整体有序序列，最终实现全序列的有序。伪代码：MERGE-SORT(A,low,high)//A[1..n]iflow

5、A,mid+1,high)MERGE(A,low,mid,high)1.1引子–归并排序示例MERGE-SORT：1.1引子–归并排序(MERGE)MERGE：1.1引子–归并排序证明：可以尝试采用循环不变式自行证明，这里略。1.1引子–归并排序运行时间分析：算法(Algorithm)：对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。算法的特性：输入（0个或多个）、输出（至少1个）、确定性（无歧义）、有限性、可行性。描述方式：自然语言、图形、程序设计语言、伪代码本书采用了面向对象程序设计语言C++，讲授时采用

6、伪代码。算法与程序的区别？1.2算法的基本概念–算法程序(Program)程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的性质(4)。例如：操作系统是一个在无限循环中执行的程序，因而其不是一个算法；操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。1.2算法的基本概念–程序会场安排问题、单源最短路径、哈夫曼编码、最小生成树排序与查找、循环赛日程表最长公共子序列、矩阵连乘、凸多边形最优三角剖分、加工顺序等N后、最大团、图的m着色0-1背包、TSP、布线问题等等1.2算法的基本概念–经典问题

7、1.2算法的基本概念–拼图游戏在n×n格的棋盘上放置彼此不受攻击的n个皇后：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子；n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQ1.2算法的基本概念–N后问题1.2算法的基本概念–0-1背包问题起点XXXXXXXXXXXXXXXXXXXX终点XXXXX1.2算法的基本概念–布线问题1.3算法设计的一般过程算法复杂性（亦称算法复杂度）为算法运行时所需计算机资源的度量：时间复杂性（影响因素

8、包括问题规模n、输入序列I、算法本身A）：T(n,I,A)T(n)空间复杂性（影响因素包括输入输出数据IO、辅助变量V、算法本身A）：S(IO,V,