算法设计与分析

1、1算法设计与分析2先修课程离散数学离散数学数据结构数据结构高级程序语言高级程序语言3参考资料1计算机算法设计与分析（第计算机算法设计与分析（第3版）版） ，王晓东，电子，王晓东，电子工业出版社工业出版社 配套：配套：“算法设计与实验题解算法设计与实验题解”，王晓东，王晓东 ，电子工，电子工业出版社业出版社 2算法设计与分析基础（算法设计与分析基础（Introduction to Design and Analysis of Algorithms） ，潘彦译（，潘彦译（美美 Anany Levitin） ，清华大学出版社，清华大学出版社 3算法设计技巧与分析（算法设计技巧与分析（Algorith

2、ms Design Techniques and Analysis），吴伟昶等译（），吴伟昶等译（沙沙特特 M.H.Alsuwaiyel），电子工业出版社），电子工业出版社 4计算机算法基础（第计算机算法基础（第2版），余祥宣、邹海明等，版），余祥宣、邹海明等，华中科技大学出版社华中科技大学出版社课件(webcc)4上机：教学楼上机：教学楼D506机房机房期末总评成绩：期末总评成绩： 平时成绩平时成绩40% + 期末期末（闭卷）成绩成绩*60% 平时成绩：考勤、书面作业平时成绩：考勤、书面作业(含实验含实验)课程介绍迟交作业，酌情扣分迟交作业，酌情扣分抄袭作弊，将导致记抄袭作弊，将导致记零分处

3、理以及零分处理以及 ！办公电话：办公电话：26535255Email:课程内容：介绍计算机课程内容：介绍计算机非数值算法非数值算法的主要设计的主要设计 方法与分析技巧方法与分析技巧5课程介绍几个例子例例1：百鸡问题百鸡问题：“鸡翁一，值钱五；鸡鸡翁一，值钱五；鸡母一，值母一，值 钱三；鸡雏三，值钱一。百钱买百鸡，钱三；鸡雏三，值钱一。百钱买百鸡，问鸡问鸡 翁、母、雏各几何？翁、母、雏各几何？” 穷举法穷举法6课程介绍几个例子例例2：假设正整数假设正整数n、s，s 259 n=5 s=2 24351 - 231 贪心法贪心法7课程介绍几个例子例例3：奥运会排球比赛奥运会排球比赛: 预赛：预赛：

4、A组：中国、古巴、日本、美国、组：中国、古巴、日本、美国、波波 兰、委内瑞拉、兰、委内瑞拉、 B组：俄罗斯、塞尔维亚、巴西、组：俄罗斯、塞尔维亚、巴西、意大意大 利、哈萨克斯坦、阿尔及利利、哈萨克斯坦、阿尔及利亚亚 1/4决赛、决赛、1/2决赛：古决赛：古 vs 美、中美、中 vs 巴巴分治法分治法8课程介绍几个例子例例4：八后问题八后问题: 在在8*8的棋盘上，每行的棋盘上，每行放置放置 一个皇后，要求它们不能在同一一个皇后，要求它们不能在同一列，列， 同一斜线上。同一斜线上。 回溯法回溯法9课程介绍本课程学习的算法 穷举法穷举法 百鸡问题百鸡问题 递归和分治递归和分治 二分查找、快速排序二

5、分查找、快速排序 贪心法贪心法 最小生成树、最短距离最小生成树、最短距离 回溯回溯 迷宫、八后问题迷宫、八后问题 动态规划动态规划 分支与限界分支与限界常用算法常用算法10教学内容与进度 第1 章 算法引论 3 学时； 第2章常用的数学工具 3 学时； 第4章 递归与分治 5学时；实验1 第5章贪心算法 4 学时； 第6章动态规划 6 学时；实验2 第7章 回溯法 5 学时；实验3 第8章 分支限界法 5学时； 第12-13 章 NP完全问题及计算复杂性 3学时 常用算法11教学内容 第12-13 章简单介绍了NP完全性理论和计算复杂性，这是当前计算机算法领域的热门研究课题，具有很高的理论价值

6、。P类和NP类问题NP完全问题计算模型 复杂性类型之间的关系 12第一章 算法的基本概念 程序程序 = 算法算法 + 数据结构数据结构 算法设计与分析是计算机科学与技术的算法设计与分析是计算机科学与技术的一个一个 核心内容核心内容.131.1 引言 算法设计与分析在算法设计与分析在 计算机科学与技术计算机科学与技术专专业中的地位业中的地位n为什么要学习算法为什么要学习算法? 理论角度理论角度:“算法不仅是计算机科学的一个算法不仅是计算机科学的一个分支分支,它更是它更是计算机科学的核心计算机科学的核心。而且。而且,可以毫可以毫不夸张地说不夸张地说,它和绝大多数的它和绝大多数的科学科学、商业和技、

7、商业和技术都是相关的。术都是相关的。” ” _算法算法: 计算的灵魂计算的灵魂 ,David Harel 实践角度实践角度: 开发分析能力开发分析能力:14计算机专业课程群建设计算机专业课程群建设自然科学基础课程群计算机科学理论课计算机科学理论课程群程群计算机硬件课程群软件基础课程群15*组合数学*形式语言与自动机*模糊数学*数理逻辑 算法设计与分析*可计算性理论*算法分析计算复杂性理论 离散数学其中：*为研究生课程 计算机科学理论课程群计算机科学理论课程群数据结构161.1 引言 算法设计与分析在算法设计与分析在 计算机科学与技术计算机科学与技术专业中的专业中的地位地位n为什么要学习算法为什

8、么要学习算法? 理论角度理论角度 实践实践/工程角度工程角度:了解计算机领域中不同问题的一了解计算机领域中不同问题的一系列系列标准算法标准算法;具备设计具备设计新算法新算法和分析其效率的能力。和分析其效率的能力。 多、快、好、省与少、慢、差、费 开发分析能力开发分析能力: “算法是一种一般性的算法是一种一般性的智能工具智能工具，一定，一定有助有助于我们对其他学科的理解于我们对其他学科的理解，为什么算法会有这种作用呢？为什么算法会有这种作用呢？我们可以这样理解：人们常说，一个人只有把知识教给我们可以这样理解：人们常说，一个人只有把知识教给“计计算机算机”，才能，才能“真正掌握它，也就是说，将知识

9、表述为一种真正掌握它，也就是说，将知识表述为一种算法，算法，比起简单地按照常规去理解事物，用算法将其形式比起简单地按照常规去理解事物，用算法将其形式化会使我们获得更加深刻的理解。化会使我们获得更加深刻的理解。” _Donald Knuth，1974图图灵奖的获得者。灵奖的获得者。171.1 引言算法定义算法定义 定义定义1.1：算法问题求解的有效策略：算法问题求解的有效策略.是是解某一特定问题的一组有穷规则的集解某一特定问题的一组有穷规则的集合。合。算法特征算法特征 有限性、确定性、输入、输出、能行有限性、确定性、输入、输出、能行性性 实用算法对有限性要求运行时间是可实用算法对有限性要求运行时

10、间是可接受的。接受的。18算法设计与分析的步骤 若一问题是可解的若一问题是可解的,则求解的全过程由以下阶则求解的全过程由以下阶段构成段构成(算法设计与分析的步骤算法设计与分析的步骤):1.问题的陈述问题的陈述2.选择模型或设计模型选择模型或设计模型=选择模型或设计模选择模型或设计模型型3.设计算法设计算法(选择选择)和确认和确认=设计算法设计算法(选择选择)和确认和确认4.分析算法分析算法 =分析算法分析算法5.程序实现程序实现=步骤的含义步骤的含义: :一个好的算法是反复努力和重新修一个好的算法是反复努力和重新修正的结果正的结果设计算法是一个非常有创造性和非常值得付出的设计算法是一个非常有创

11、造性和非常值得付出的过程过程. .课程的目的就是想证明这个事实课程的目的就是想证明这个事实. .191.1 引言算法设计的例子算法设计的例子穷举法穷举法 穷举法：穷举法：是从有限集合中，逐一列举是从有限集合中，逐一列举集合集合 的所有元素，对每一个元素逐一判断的所有元素，对每一个元素逐一判断和处和处 理，找出问题的解。理，找出问题的解。20 例例1.1 百鸡问题百鸡问题：“鸡翁一，值钱五；鸡鸡翁一，值钱五；鸡母一，母一， 值钱三；鸡雏三，值钱一。百钱买百鸡，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡问鸡 翁、母、雏各几何？翁、母、雏各几何？” 这里讨论更一般的这里讨论更一般的n钱买钱买n鸡问题鸡

12、问题. 穷举法实例问题的陈述问题的陈述21解：设鸡翁、鸡母、鸡雏分别为解：设鸡翁、鸡母、鸡雏分别为a,b,c只。只。 测试集合：测试集合： 0an 0bn 0cn 判断条件：判断条件：a+b+c = n 5*a+3*b+c/3 = n 且且 c%3 = 0 穷举法实例百鸡问题选择模型或设计模型选择模型或设计模型设计算法设计算法算法描述如下：算法描述如下：22 输入：输入：n 输出：满足问题的解数目输出：满足问题的解数目k,公鸡、母鸡、小公鸡、母鸡、小鸡的鸡的 只数只数g 、m 、s void childen_question(int n, int &k, int g ,int m ,i

13、nt s );穷举法实例百鸡问题设计算法设计算法23void childen_question(int n,int &k,int g,int m,int s) int a,b,c; k=0; for(a=0; a=n; a+) for(b=0; b=n; b+) for(c=0; c=n; c+) if(!(c%3)&a+b+c=n & 5*a+3*b+c/3=n) gk=a; mk=b; sk=c; k+; 设计算法设计算法算法的复杂性分析算法的复杂性分析24 测试集合：测试集合： 0an/5 0bn/3 c = n-a-b 判断条件：判断条件：5*a+3*b+c/3

14、 = n 且且 c%3 = 0 算法描述如下算法描述如下(算法算法1.2)：穷举法实例百鸡问题25void childen_question(int n,int &k,int g,int m, int s)1 int a,b,c; 2 int n1=n/5, n2=n/3; k=0; /53 for(a=0; a=n1; a+) /1+2(n/5+1)4 for(b=0; b=n2; b+) /n/5+1+2(n/5+1)(n/3+1)5 6 c = 100-a-b; /3(n/5+1) (n/3+1)7 if(!(c%3) & 5*a+3*b+c/3=n)8 /10(n/5+

15、1) (n/3+1)9 gk=a; mk=b; sk=c;10 k+; /4(n/5+1) (n/3+1)11 12 算法的复杂性分析算法的复杂性分析26 例例1.2 货郎担问题货郎担问题：某售货员要到若干：某售货员要到若干个城市销售货物，已知各城市之间的个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及距离，要求售货员选择出发的城市及旅行线路使每个城市仅经过一次，最旅行线路使每个城市仅经过一次，最后回到原出发城市，而总路程最短。后回到原出发城市，而总路程最短。 穷举法实例货郎担问题27解：解：假设假设n个城市，分别用个城市，分别用1到到n的数字编号，的数字编号， 问题归结为在有

16、向网中问题归结为在有向网中(顶点表示城市顶点表示城市,弧上弧上 权重表示距离权重表示距离)，寻找一条路径最短，寻找一条路径最短，n个城个城 市仅经过一次的回路市仅经过一次的回路(哈密尔顿回路哈密尔顿回路)。 测试集合：测试集合： 1,n的排列对应一条回路的排列对应一条回路,如如2356n12 全部排列构成测试集合全部排列构成测试集合 穷举法实例货郎担问题28判断条件：判断条件：选择排列中路径和最小的回路。选择排列中路径和最小的回路。假设用邻接矩阵假设用邻接矩阵c存储网，算法描述如下：存储网，算法描述如下：输入：城市数输入：城市数n,c 输出：最短距离输出：最短距离min，旅行路线，旅行路线t

17、void salesman_problem(int n, float min, int t ,float c );穷举法实例货郎担问题29void salesman_problem(int n, float min, int t,float c);int pn,i=1,m=n!; float cost; min = MAX_FLOAT_NUM; while(i=m) 产生产生n个城市的第个城市的第i个排列于个排列于p; cost = 回路回路p的权重和；的权重和； if(cost min) min = cost; p复制至复制至t; i+; 30表1.1 算法1.3的执行时间随n的增长而增长的

18、情况nn!nn!nn!nn!5120ss9362ms 131.72h17 11.27year6720ss103.62s1424h18203year75.04ms1139.9s1515day19 3857year840.3ms12479.0s16 242day 2077146year注：表注：表1.1假设算法假设算法1.3中中while循环体执行一次需循环体执行一次需1s。对某类特定问题，穷举法只适用于规模较小的情况。对某类特定问题，穷举法只适用于规模较小的情况。穷举法实例货郎担问题31ACM 与算法设计1、穷举法、穷举法如求素数 、百钱百鸡问题2、分治法、分治法如汉诺塔问题、折半查找算法、快速

19、排序算法 3、贪心法、贪心法如：哈夫曼算法、最小生成树、最短路径算法找硬币问题 32ACM 与算法设计4、回溯法、回溯法如全排列问题、迷宫、迷宫、 N后问题5、动态规划法、动态规划法6、分支限界法、分支限界法 如货郎担问题货郎担问题、作业分配问题如货郎担问题、货郎担问题、最短路径、资源分配问题33（1）如何设计算法；）如何设计算法；（2）如何评价算法的效率）如何评价算法的效率 时间复杂性：时间复杂性：算法的执行时间算法的执行时间 空间复杂性：空间复杂性：算法所需的存储空间算法所需的存储空间 算法设计目标：算法设计目标：时间复杂性、空间复杂性时间复杂性、空间复杂性低低 1.1 引言 算法的复杂性

20、分析主主 要要341.2 算法的时间复杂性 算法的输入规模和运行时间的阶算法的输入规模和运行时间的阶 算法的执行时间随问题规模的增大而增大，算法的执行时间随问题规模的增大而增大，故故 常用常用关于关于问题规模问题规模n的函数估算算法在大的函数估算算法在大规模问题时的运行时间。规模问题时的运行时间。35运行时间T(n)的估算运行时间运行时间T(n)的估算的估算 假设假设初等操作初等操作计算模型：计算模型：所有操作数都具所有操作数都具有相同的固定字长；所有操作的时间花费都有相同的固定字长；所有操作的时间花费都是一个常数时间间隔。是一个常数时间间隔。 如：算术运算；比较和逻辑运算；赋值运算如：算术运

21、算；比较和逻辑运算；赋值运算(含遍历表和指针赋值）含遍历表和指针赋值）等。等。 例例1.3 估算算法估算算法1.1的运行时间的运行时间T1(n)。36void childen_question(int n,int &k,int g,int m, int s) int a,b,c; k=0; for(a=0; a=n; a+) for(b=0; b=n; b+) for(c=0; c0 T1*(n)的阶是3。 实际中，通常用渐进时间复杂性衡量一个算法的实际中，通常用渐进时间复杂性衡量一个算法的 时间复杂性。时间复杂性。 练习练习1.1：估算算法估算算法1.2的和的和T2*(n)，并说明，

22、并说明T2*(n)的阶。的阶。渐进时间复杂性T*(n)T2(n) =19n2/15+164n/15+30T1(n) 20n3 +64n2 +72n +3140常用的有常用的有: logn、n、nlogn、n2、n3、2n 当当n足够大时，足够大时， logn n nlogn n2 n3 0; i-) value = value*x+Ai-1; return value;73按初等操作计算模型分析算法按初等操作计算模型分析算法1.41.4的执行时间：的执行时间：)(353) 1( 21)(nnnnnT算法算法1.4的循环次数是的循环次数是n次，与次，与T(n)的阶相同，的阶相同，均为均为 。)(

23、n分析复杂性时，只需分析算法中的循环次数的阶。分析复杂性时，只需分析算法中的循环次数的阶。时间复杂性分析 循环次数统计例74设：设：c1：给循环控制变量：给循环控制变量i 赋初值所花费的单位赋初值所花费的单位时间时间c2：变量：变量i的测试及递减、以及值的测试及递减、以及值value的的计算所花费的单位时间。计算所花费的单位时间。 算法的执行时间算法的执行时间T(n)为：为：)()(21nnccnT结论：结论：循环次数循环次数n n( (问题规模) )是算法运行时间是算法运行时间的阶的阶011)()(axaxaxaxPnn75 例：分析以下程序段的时间复杂度。 for(k=1; kn ; k+

24、) y = y+1; for(k=1; kn ; k+) y = y+1; for(j=0; j=(2*n); j+) x+; O(n)O(n2)随堂练习76 for(k=0; kn ; k+) for( m=0; m= k; m+) Akm = m+k;O(n2) for(k=0; kn; k+) for( m=0; mn; m+) Ckm = 0; for(j=0; j0; k+) for(i=0; iAi+1) swap(Ai,Ai+1); 时间复杂性分析 循环次数统计例(n(n2 2) )791.3.2基本操作频率的统计1. 基本操作基本操作的定义定义定义1.8 -基本操作基本操作:算

25、法中的某个算法中的某个初等初等操作，如果操作，如果它的最高执行频率和所有其它初等操作的最高执它的最高执行频率和所有其它初等操作的最高执行频率，相差在一个常数因子之内，就说这个初行频率，相差在一个常数因子之内，就说这个初等操作是一个等操作是一个基本操作基本操作。 基本操作基本操作的选择，必须的选择，必须反映反映出该出该操作随着输入操作随着输入 规模的增加而变化规模的增加而变化的情况。的情况。 例：例：算法算法1.51.5中第中第5 5行行forfor循环语句中的条件循环语句中的条件比较比较操作，第操作，第6 6行的行的赋值、乘法赋值、乘法操作都可以选作为基本操作。操作都可以选作为基本操作。80一

26、般：一般： 检索和排序检索和排序问题，可选元素问题，可选元素比较操作比较操作作为基本操作作为基本操作 矩阵乘法矩阵乘法问题，可选问题，可选数乘数乘作为基本操作作为基本操作 遍历链表遍历链表问题，可选问题，可选设置设置或或更新链表指针更新链表指针作为基本操作为基本操作作 图的遍历图的遍历问题，可选问题，可选访问图中的顶点访问图中的顶点的操作作为基本的操作作为基本操作操作 一般：一般：先确定先确定基本操作基本操作，再，再利用利用、 、或、或 ，去去寻找执寻找执行行该该基本操作基本操作的阶的阶，也是算法运行时间的阶。，也是算法运行时间的阶。 例：例：算法算法1.51.5中中选选第第6 6行的行的乘法

27、乘法操作为基本操作。操作为基本操作。812. 用基本操作的执行频率估计算法的时间复杂性用基本操作的执行频率估计算法的时间复杂性 一般：一般：先确定先确定基本操作基本操作，再，再利用利用、 、或、或 ，去去寻找执寻找执行行该该基本操作基本操作的阶的阶，也就是算法运行时间的阶。，也就是算法运行时间的阶。 例：例：算法算法1.51.5中中选选第第6 6行的行的乘法乘法操作为基本操作，则操作为基本操作，则)()(ncnnT822. 用基本操作的执行频率估计算法的时间复杂性用基本操作的执行频率估计算法的时间复杂性 例例1.131.13 合并两个有序的子数组合并两个有序的子数组( (略略) ) 计算步的统

28、计计算步的统计(自学，简单了解）自学，简单了解）83有些算法的运行时间除与问题规模有关外，还与有些算法的运行时间除与问题规模有关外，还与输输入元素的初始排列顺序有关。因此，有入元素的初始排列顺序有关。因此，有3种分析种分析方法：方法：依据输入元素顺序，算法所达到的最依据输入元素顺序，算法所达到的最短运短运行时间。行时间。依据输入元素顺序，算法所达到的最依据输入元素顺序，算法所达到的最长运长运行时间。行时间。算法的运行时间取算法所有可能输入算法的运行时间取算法所有可能输入的平的平均运行时间。均运行时间。 平均情况平均情况：最好情况、最坏情况、平均情况分析最好情况、最坏情况、平均情况分析84练习练

29、习1.41.4： 分析下列算法的最好情况、最坏情况、分析下列算法的最好情况、最坏情况、平均情况的时间复杂性平均情况的时间复杂性. . 输入：输入：数组数组A，元素个数，元素个数n输出：输出：按递增顺序排列的数组按递增顺序排列的数组A最好情况、最坏情况、平均情况分析例最好情况、最坏情况、平均情况分析例85void insert_sort(int A, int n)int a,i,j; for(i=1; i=0 & Aja) /* 非递增*/ Aj+1 = Aj; j-; Aj+1 = a; 86最好情况：最好情况：最坏情况：最坏情况：)(nwhile复杂性为不执行。故时间，元素按升序排列

30、。此时)(2nwhile故时间复杂性为每次执行最大次数，元素按降序排列。此时最好情况、最坏情况、平均情况分析例最好情况、最坏情况、平均情况分析例87平均情况：平均情况：假设元素在各位置的插入概率相等。假设元素在各位置的插入概率相等。设前设前i-1个元素排好序，现插入第个元素排好序，现插入第i个元素。个元素。第第i个元素的插入位置有个元素的插入位置有i个，对应的比较次数为个，对应的比较次数为i-1、i-1、i-2、1。因此插入第。因此插入第i个元素的平均比较个元素的平均比较次数为：次数为： 最好情况、最坏情况、平均情况分析例最好情况、最坏情况、平均情况分析例iiijiiTiji122111188

31、最好情况、最坏情况、平均情况分析例最好情况、最坏情况、平均情况分析例直插算法要插入第直插算法要插入第2,3,.,n个元素，因此平均个元素，因此平均比较总次数为：比较总次数为： 0.57721.C C) (ln)3(41lim1)3(41)1221(21222nnnTinniiTTnnininii平均情况下的时间复杂性是平均情况下的时间复杂性是(n(n2 2) )。891.4 算法的空间复杂性分析算法的空间复杂性，指的是为解一个问题实例而算法的空间复杂性，指的是为解一个问题实例而需需要的存储空间。有两种分析方法：要的存储空间。有两种分析方法：算法所需的工作空间算法所需的工作空间 不包含存储输入数据、程序代码和常数的空间，不包含存储输入数据、程序代码和常数的空间， 仅包含算法函数体内新生成的变量空间。仅包含算法函数体内新生成的变量空间