算法及其基础.pptx
本章的要点与难点要点:理解算法的概念。程序与算法的区别和联系；理解算法设计的一般过程；掌握用C+/JAVA语言以及伪代码描述算法的方法；掌握算法的计算复杂性概念及分析。难点:算法的计算复杂性（主要指时间复杂性）分析。第1页/共39页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、堆、快速、组合排序等，不稳定的。第2页/共39页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=key第3页/共39页1.1 引子 插入排序n示例：示例：第4页/共39页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、且已排好序的各个元素。第5页/共39页1.1 引子 插入排序n运行时间分析：运行时间分析：v最坏情况最坏情况：T(n)=O(n2)。，算术级数。已非升序排序；v平均情况平均情况：T(n)=O(n2)。，算术级数；v最好情况：T(n)=O(n)。，已升序排序。第6页/共39页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)第7页/共39页1.1 引子 归并排序示例nMERGE-SORT：第8页/共39页1.1 引子 归并排序(MERGE)nMERGE：第9页/共39页1.1 引子 归并排序n证明：证明：v可以尝试采用循环不变式自行证明，这里略。可以尝试采用循环不变式自行证明，这里略。第10页/共39页1.1 引子 归并排序n运行时间分析：运行时间分析：第11页/共39页算法(Algorithm)：对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。算法的特性：输入（0个或多个）、输出（至少1个）、确定性（无歧义）、有限性、可行性。描述方式：自然语言、图形、程序设计语言、伪代码本书采用了面向对象程序设计语言C+，讲授时采用伪代码。算法与程序的区别？1.2 算法的基本概念 算法第12页/共39页程序(Program)程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的性质(4)。例如：操作系统是一个在无限循环中执行的程序，因而其不是一个算法；操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。1.2 算法的基本概念 程序第13页/共39页会场安排问题、单源最短路径、哈夫曼编码、最小生成树排序与查找、循环赛日程表最长公共子序列、矩阵连乘、凸多边形最优三角剖分、加工顺序等N后、最大团、图的m着色0-1背包、TSP、布线问题等等1.2 算法的基本概念 经典问题第14页/共39页1.2 算法的基本概念 拼图游戏第15页/共39页p在在nnnn格的棋盘上放置格的棋盘上放置彼此不受攻击的彼此不受攻击的n n个皇后：个皇后：u按照国际象棋的规则，皇后可以攻击与之处在 同一行 或 同一列 或 同一斜线 上的棋子；un后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQ1.2 算法的基本概念 N后问题第16页/共39页1.2 算法的基本概念 0-1背包问题第17页/共39页起点起点 XXXXXXXXXXXXXXXXXXXX终点终点XXXXX1.2 算法的基本概念 布线问题第18页/共39页1.3 算法设计的一般过程第19页/共39页算法复杂性（亦称算法复杂度）为算法运行时所需计算机资源的度量：时间复杂性（影响因素包括问题规模n、输入序列I、算法本身A）：T(n,I,A)T(n)空间复杂性（影响因素包括输入输出数据IO、辅助变量V、算法本身A）：S(IO,V,A)S(V)很显然：算法所需资源越多，算法的复杂性就越高；算法所需资源越少，算法的复杂性就越低。1.4 算法分析 算法复杂性第20页/共39页算法分析：对算法的时间复杂性和空间复杂性进行分析，这里主要还是指对算法的时间复杂性的分析。方法：事后统计 和 事前分析算法分析的意义：算法设计：复杂性尽可能的低；算法选用：选择复杂性最低的算法；算法改进：算法分析有助于算法的改进。1.4 算法分析第21页/共39页影响算法运行时间的因素（除算法本身外）：机器；采用语言及编译程序；编程能力等。算法分析无需具体时间（精确或近似）：针对同一问题不同算法的比较，相对而非绝对；应该独立于机器及实现语言；无论科技如何发展，其运行时间的测度应始终成立；关心的是大的问题规模时的运行情况。渐近复杂性1.4 算法分析 第22页/共39页算法渐近复杂性态：设算法的运行时间为T(n)，如果存在T*(n)，使得 就称T*(n)为算法的渐近性态或渐近时间复杂性。1.4 算法分析 算法渐近复杂性态?第23页/共39页假设算法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 算法分析 算法渐近复杂性态示例第24页/共39页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秒第25页/共39页渐近意义下的记号：O、渐近上界-O(big o)渐近下界-(big)渐近精确界-(big)o、和1.4 算法分析 渐近复杂性记号第26页/共39页渐近上界-O(big o):设f(N)和g(N)是定义在正数集上的正函数，下同。定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)。即f(N)的阶不高于g(N)的阶。求T(n)=10n+4的渐近上界O：O(n)1.4 算法分析 渐近上界第27页/共39页根据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运算规则第28页/共39页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)为渐近正函数记忆三种情况，见主定理。1.4 算法分析 递归算法的复杂性分析第35页/共39页n运行时间分析（归并排序算法）：运行时间分析（归并排序算法）：1.4 算法分析 递归树示例1第36页/共39页n运行时间分析：运行时间分析：1.4 算法分析 递归树示例2第37页/共39页1.5 相关基础n数据结构：数据结构：v顺序表与链表v栈与队列v树与图v集合n数学公式：数学公式：v对数公式v组合公式v求和公式v向上取整和向下取整公式第38页/共39页谢谢您的观看！第39页/共39页
