算法及其基础详解演示文稿

算法及其基础详解演示文稿当前1页，总共38页。（优选）算法及其基础当前2页，总共38页。本章的要点与难点要点:

理解算法的概念。程序与算法的区别和联系；理解算法设计的一般过程；掌握用C++/JAVA语言以及伪代码描述算法的方法；掌握算法的计算复杂性概念及分析。难点:算法的计算复杂性（主要指时间复杂性）分析。当前3页，总共38页。1.1引子–排序问题排序问题描述：输入：数字序列X=<a1,a2,…,an>输出：一个排列X‘=<a‘1,a‘2,…,a‘n>，数字序列X和排列X‘之间为满射或一一映射（即元素一一对应），并且有a‘1≤a‘2≤…≤a‘n（元素间非减序）。例如：输入：8,2,4,9,3,6输出：2,3,4,6,8,9排序方法：冒泡、插入、归并、二叉树、桶排序等。稳定的；选择、Shell、堆、快速、组合排序等，不稳定的。当前4页，总共38页。1.1引子–插入排序原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。伪代码：INSERTION-SORT(A,n)//A[1..n]forj=2tondokey=A[j]i=j-1

whilei>0andA[i]>keydoA[i+1]=A[i]i=i-1A[i+1]=key当前5页，总共38页。1.1引子–插入排序示例：当前6页，总共38页。1.1引子–插入排序证明–基于循环不变式(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]、且已排好序的各个元素。当前7页，总共38页。1.1引子–插入排序运行时间分析：最坏情况：T(n)=O(n2)。，算术级数。已非升序排序；平均情况：T(n)=O(n2)。

，算术级数；最好情况：T(n)=O(n)。，已升序排序。当前8页，总共38页。1.1引子–归并排序原理：基于分而治之思想，递归地把待排序序列分解为若干子序列并进行排序，再把已排序的子序列合并为整体有序序列，最终实现全序列的有序。伪代码：MERGE-SORT(A,low,high)//A[1..n]iflow<highthenmid=(low+high)/2MERGE-SORT(A,low,mid)MERGE-SORT(A,mid+1,high)MERGE(A,low,mid,high)当前9页，总共38页。1.1引子–归并排序示例MERGE-SORT：当前10页，总共38页。1.1引子–归并排序(MERGE)MERGE：当前11页，总共38页。1.1引子–归并排序证明：可以尝试采用循环不变式自行证明，这里略。当前12页，总共38页。1.1引子–归并排序运行时间分析：当前13页，总共38页。算法(Algorithm)：对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。

算法的特性：输入（0个或多个）、输出（至少1个）、确定性（无歧义）、有限性、可行性。描述方式：自然语言、图形、程序设计语言、伪代码本书采用了面向对象程序设计语言C++，讲授时采用伪代码。算法与程序的区别？1.2算法的基本概念–算法当前14页，总共38页。程序(Program)程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的性质(4)。例如：操作系统是一个在无限循环中执行的程序，因而其不是一个算法；操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。1.2算法的基本概念–程序当前15页，总共38页。会场安排问题、单源最短路径、哈夫曼编码、最小生成树排序与查找、循环赛日程表最长公共子序列、矩阵连乘、凸多边形最优三角剖分、加工顺序等N后、最大团、图的m着色0-1背包、TSP、布线问题等等1.2算法的基本概念–经典问题当前16页，总共38页。1.2算法的基本概念–拼图游戏当前17页，总共38页。在n×n格的棋盘上放置彼此不受攻击的n个皇后：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子；n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQ1.2算法的基本概念–N后问题当前18页，总共38页。1.2算法的基本概念–0-1背包问题当前19页，总共38页。起点

XXXXXXXXXXXXXXXXXXXX终点XXXXX1.2算法的基本概念–布线问题当前20页，总共38页。1.3算法设计的一般过程当前21页，总共38页。算法复杂性（亦称算法复杂度）为算法运行时所需计算机资源的度量：时间复杂性（影响因素包括问题规模n、输入序列I、算法本身A）：T(n,I,A)T(n)空间复杂性（影响因素包括输入输出数据IO、辅助变量V、算法本身A）：S(IO,V,A)S(V)很显然：算法所需资源越多，算法的复杂性就越高；算法所需资源越少，算法的复杂性就越低。1.4算法分析–算法复杂性当前22页，总共38页。算法分析：对算法的时间复杂性和空间复杂性进行分析，这里主要还是指对算法的时间复杂性的分析。方法：事后统计和事前分析算法分析的意义：算法设计：复杂性尽可能的低；算法选用：选择复杂性最低的算法；算法改进：算法分析有助于算法的改进。1.4算法分析当前23页，总共38页。影响算法运行时间的因素（除算法本身外）：机器；采用语言及编译程序；编程能力等。算法分析无需具体时间（精确或近似）：针对同一问题不同算法的比较，相对而非绝对；应该独立于机器及实现语言；无论科技如何发展，其运行时间的测度应始终成立；关心的是大的问题规模时的运行情况。渐近复杂性1.4算法分析–当前24页，总共38页。算法渐近复杂性态：设算法的运行时间为T(n)，如果存在T*(n)，使得

就称T*(n)为算法的渐近性态或渐近时间复杂性。1.4算法分析–算法渐近复杂性态?当前25页，总共38页。假设算法A的运行时间表达式为T1(n)：

T1(n)=30n4+20n3+40n2+46n+100

T*1(n)≈n4（阶）假设算法B的运行时间表达式为T2(n)：

T2(n)=1000n3+50n2+78n+10

T*2(n)≈n3（阶）1.4算法分析–算法渐近复杂性态示例当前26页，总共38页。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秒当前27页，总共38页。渐近意义下的记号：O、Ω、Θ渐近上界-O(bigo)渐近下界-Ω(bigω)渐近精确界-Θ(bigθ)o、ω和θ1.4算法分析–渐近复杂性记号当前28页，总共38页。渐近上界-O(bigo):设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算法分析–渐近上界当前29页，总共38页。根据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运算规则当前30页，总共38页。常见的几类算法复杂性：O(1)：常数阶；O(log2n),O(nlog2n)：对数阶；O(n),O(n2),O(n3),…,O(nm)：多项式阶。多项式时间算法；O(2n),O(n!),O(nn)：指数阶。指数时间算法。几类复杂性之间的关系：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n)<O(n2)<O(n3)<…<O(nm)<O(2n)<O(n!)<O(nn)1.4算法分析–常见几类复杂性当前31页，总共38页。Ω(bigomega)：如存在正的常数c和自然数n0，使得当nn0时有f(n)cg(n)，则称函数f(n)当n充分大时下有界，且g(n)是它的一个下界，记为f(N)=Ω(g(n))。即f(n)的阶不低于g(n)的阶。Θ(bigtheta)：如存在正的常数c1,c2和自然数n0，使得当nn0时,有c1g(n)f(n)c2g(n)，则称g(n)和f(n)同阶。o、ω和θ与O、Ω和Θ。1.4算法分析–渐近复杂性记号2当前32页，总共38页。求T(n)=30n4+20n3+40n2+46n+100的渐近下界Ω：Ω(n4)求T(n)=20n2+8n+10的渐近精确界Θ：Θ(n2)求T(n)=amnm+am-1nm-1+…+a1n+a0的渐近上界O、下界Ω和精确界Θ：O(nm)、Ω(nm)和Θ(nm)1.4算法分析–渐近界示例当前33页，总共38页。1.4算法分析–渐近界示例当前34页，总共38页。非递归算法：顺序语句：各语句计算时间相加；选择语句：条件判定语句以及各分支中语句计算时间的较大者；循环语句：循环体内计算时间*循环次数，还需考虑循环判定条件；对于嵌套循环：循环体内计算时间*所有循环次数。1.4算法分析–非递归当前35页，总共38页。递归定义：子程序（或函数）直接调用自己或通过一系列调用语句间接调用自已，称为递归。直接或间接调用自身的算法称为递归算法。采用递归算法来求解问题的一般步骤：分析问题，寻找递归关系；找出停止条件；构建递归体。递归应用实例：Fibonacci数列Hanoi塔归并算法等1.4算法