算法及其基础.pptx

第一章 算法及其基础n1.1 引子引子n1.2 算法的基本概念算法的基本概念n1.3 算法设计的一般过程算法设计的一般过程n1.4 算法分析算法分析n1.5 相关基础相关基础本章的要点与难点n要点要点:v 理解算法的概念。程序与算法的区别和联系；v 理解算法设计的一般过程；v 掌握用C+/JAVA语言以及伪代码描述算法的方法；v 掌握算法的计算复杂性概念及分析。n难点难点:v 算法的计算复杂性（主要指时间复杂性）分析。1.1 引子 排序问题n排序问题描述：排序问题描述：v输入输入：数字序列X=v输出输出：一个排列X=，数字序列X和排列X之间为满射或一一映射（即元素一一对应），并且有a1 a2 an（元素间非减序）。v例如：例如：输入：8,2,4,9,3,6输出：2,3,4,6,8,9n排序方法：排序方法：v冒泡、插入插入、归并归并、二叉树、桶排序等。稳定的；v选择、Shell、堆、快速、组合排序等，不稳定的。1.1 引子 插入排序n原理：原理：v通过构建有序序列，对于未排序数据，在已排序序列通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入中从后向前扫描，找到相应位置并插入。n伪代码：伪代码：INSERTION-SORT(A,n)/A1.nINSERTION-SORT(A,n)/A1.n for j=2 to n do key=Aj i=j-1 while i 0 and Ai key do Ai+1=Ai i=i-1 Ai+1=key1.1 引子 插入排序n示例：示例：1.1 引子 插入排序n证明证明 基于循环不变式基于循环不变式(Loop Invariant)：v循环不变式：循环不变式：在每次循环迭代之前，子数组A1.j-1已包含了最初位于A1.j-1、但已排好序的各个元素。v初始化初始化：第一轮迭代之前（即j=2），子数组A1.j-1（即A1）显然保持了循环不变式；v保持保持：假设第j次迭代之前循环不变式为真。该算法的第j次操作只是将Aj与已有序的A1.j-1中的元素进行比较，找到合适位置并插入。j+1次迭代之前，很显然A1.(j+1)-1也保持了循环不变式；v终止终止：j=n+1时，显然A1.(n+1)-1（即A1.n）已包含了最初位于A1.n、且已排好序的各个元素。1.1 引子 插入排序n运行时间分析：运行时间分析：v最坏情况最坏情况：T(n)=O(n2)。，算术级数。已非升序排序；v平均情况平均情况：T(n)=O(n2)。，算术级数；v最好情况：T(n)=O(n)。，已升序排序。1.1 引子 归并排序n原理：原理：v基于分而治之思想，递归地把待排序序列分解为若干基于分而治之思想，递归地把待排序序列分解为若干子序列并进行排序，再把已排序的子序列合并为整体子序列并进行排序，再把已排序的子序列合并为整体有序序列，最终实现全序列的有序。有序序列，最终实现全序列的有序。n伪代码：伪代码：MERGE-SORT(A,low,high)/A1.nMERGE-SORT(A,low,high)/A1.n if low high then mid=(low+high)/2 MERGE-SORT(A,low,mid)MERGE-SORT(A,mid+1,high)MERGE(A,low,mid,high)1.1 引子 归并排序示例nMERGE-SORT：1.1 引子 归并排序(MERGE)nMERGE：1.1 引子 归并排序n证明：证明：v可以尝试采用循环不变式自行证明，这里略。可以尝试采用循环不变式自行证明，这里略。1.1 引子 归并排序n运行时间分析：运行时间分析：n算法算法(Algorithm)：v对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。n算法的特性：算法的特性：v输入输入（0个或多个）、个或多个）、输出输出（至少（至少1个）、个）、确定性确定性（无（无歧义）、歧义）、有限性、可行性。有限性、可行性。n描述方式：描述方式：v自然语言、图形、程序设计语言、伪代码v本书采用了面向对象程序设计语言C+，讲授时采用伪代码。n算法与程序的区别？算法与程序的区别？1.2 算法的基本概念 算法n程序(Program)v程序是算法用某种程序设计语言的具体实现；v程序可以不满足算法的性质(4)。例如：操作系统是一个在无限循环中执行的程序，因而其不是一个算法；操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。1.2 算法的基本概念 程序n会场安排问题、单源最短路径、哈夫曼编码、最小会场安排问题、单源最短路径、哈夫曼编码、最小生成树生成树n排序与查找、循环赛日程表排序与查找、循环赛日程表n最长公共子序列、矩阵连乘、凸多边形最优三角剖最长公共子序列、矩阵连乘、凸多边形最优三角剖分、加工顺序等分、加工顺序等nN后、最大团、图的后、最大团、图的m着色着色n0-1背包、背包、TSP、布线问题、布线问题n等等等等1.2 算法的基本概念 经典问题1.2 算法的基本概念 拼图游戏p在在nnnn格的棋盘上放置格的棋盘上放置彼此不受攻击的彼此不受攻击的n n个皇后：个皇后：u按照国际象棋的规则，皇后可以攻击与之处在 同一行 或 同一列 或 同一斜线 上的棋子；un后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQ1.2 算法的基本概念 N后问题1.2 算法的基本概念 0-1背包问题起点起点 XXXXXXXXXXXXXXXXXXXX终点终点XXXXX1.2 算法的基本概念 布线问题1.3 算法设计的一般过程n算法复杂性（亦称算法复杂度）为算法运行时所算法复杂性（亦称算法复杂度）为算法运行时所需计算机资源的度量：需计算机资源的度量：v时间复杂性时间复杂性（影响因素包括问题规模n、输入序列I、算法本身A）：T(n,I,A)T(n)v空间复杂性空间复杂性（影响因素包括输入输出数据IO、辅助变量V、算法本身A）：S(IO,V,A)S(V)n很显然：很显然：v算法所需资源越多，算法的复杂性就越高；算法所需资源越多，算法的复杂性就越高；v算法所需资源越少，算法的复杂性就越低。算法所需资源越少，算法的复杂性就越低。1.4 算法分析 算法复杂性n算法分析：算法分析：v对算法的时间复杂性和空间复杂性进行分析，这里主要还是指对算法的时间复杂性的分析。v方法方法：事后统计 和 事前分析n算法分析的意义：算法分析的意义：v算法设计算法设计：复杂性尽可能的低；v算法选用算法选用：选择复杂性最低的算法；v算法改进算法改进：算法分析有助于算法的改进。1.4 算法分析n影响算法运行时间的因素（除算法本身外）：影响算法运行时间的因素（除算法本身外）：v机器；v采用语言及编译程序；v编程能力等。n算法分析无需具体时间（精确或近似）：算法分析无需具体时间（精确或近似）：v针对同一问题不同算法的比较，相对而非绝对；v应该独立于机器及实现语言；v无论科技如何发展，其运行时间的测度应始终成立；v关心的是大的问题规模时的运行情况。渐近复杂性渐近复杂性1.4 算法分析 n算法渐近复杂性态：算法渐近复杂性态：设算法的运行时间为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+10 T*2(n)n3（阶）（阶）1.4 算法分析 算法渐近复杂性态示例1.4 算法分析 几类阶的增长趋势nLog2nnnlog2nn2n32nn!103.3103.3*101021031033.6*1061026.61026.6*1021041061.3*10309.3*10157103101031.0*1041061091.1*103014*102567增长趋势：增长趋势：1个基本操作花个基本操作花1ns=10-6秒秒1年年=31536000秒秒=3.15*107秒秒渐近意义下的记号：渐近意义下的记号：O、n渐近上界渐近上界-O(big o)n渐近下界渐近下界-(big)n渐近精确界渐近精确界-(big)no、和和1.4 算法分析 渐近复杂性记号n渐近上界渐近上界-O(big o):v设f(N)和g(N)是定义在正数集上的正函数，下同。v定义定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)。v即f(N)的阶不高于不高于g(N)的阶。n求T(n)=10n+4的渐近上界O：vO(n)1.4 算法分析 渐近上界根据根据O的定义，容易证明它有如下运算规则：的定义，容易证明它有如下运算规则：(1)O(f)+O(g)=O(max(f,g)；(2)O(f)+O(g)=O(f+g)；(3)O(f)O(g)=O(fg)；(4)如 g(N)=O(f(N)，则(f)+O(g)=O(f)；(5)O(cf(N)=O(f(N)，其中c是一个正的常数；(6)f=O(f)。1.4 算法分析 渐近上界O运算规则p常见的几类算法复杂性：常见的几类算法复杂性：uO(1)：常数阶；uO(log2n),O(nlog2n)：对数阶；uO(n),O(n2),O(n3),O(nm)：多项式阶。多项式时间算法；uO(2n),O(n!),O(nn)：指数阶。指数时间算法。p几类复杂性之间的关系：几类复杂性之间的关系：O(1)O(log2n)O(n)O(nlog2n)O(n)O(n2)O(n3)O(nm)O(2n)O(n!)1，f(n)为渐近正函数v记忆三种情况，见主定理。1.4 算法分析 递归算法的复杂性分析n运行时间分析（归并排序算法）：运行时间分析（归并排序算法）：1.4 算法分析 递归树示例1n运行时间分析：运行时间分析：1.4 算法分析 递归树示例21.5 相关基础n数据结构：数据结构：v顺序表与链表v栈与队列v树与图v集合n数学公式：数学公式：v对数公式v组合公式v求和公式v向上取整和向下取整公式