算法及其基础-课件

算法及其基础 本章的要点与难点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)/A1INSERTION-SORT(A,n)/A1、nn 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)/A1MERGE-SORT(A,low,high)/A1、nn 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 算法分析 递归树示例1感谢您的聆听！