《算法分析与设计第1章详解》由会员分享，可在线阅读，更多相关《算法分析与设计第1章详解（60页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析算法设计与分析福州大学数计福州大学数计(软件软件)学院学院 陈家瑞陈家瑞1课程安排课程安排总学时：总学时：3232考查方式：闭卷考试考查方式：闭卷考试(80%)+(80%)+出勤作业出勤作业(20(20%)%)2教材教材计算机算法设计与分析（第4版）王晓东 编著电子工业出版社3参考书参考书1算法设计与分析-C+语言描述(第2版)陈慧南 编著电子工业出版社4参考书参考书2算法导论(原书第3版)Thomas H.Cormen 等著, 殷建平 等译机械工业出版社5课程主要内容课程主要内容n 第1章 算法概述n第2章 递归与分治策略n第3章 动态规划n第4章 贪心算法n第5章 回溯法n第
2、6章 分支限界法6第第1章章 算法概述算法概述学习要点学习要点: 1.1 理解算法的基本概念。1.2 掌握算法的复杂性分析。1.3 理解NP完全性理论相关知识。71.1 算法的基本概念算法的基本概念1.1.1 为什么要学习算法1.1.2 算法及其重要性质1.1.3 算法的描述方法1.1.4 问题求解的一般过程1.1.5 重要的问题类型81.1.1 为什么要学习算法为什么要学习算法理由1：算法程序的灵魂问题的求解过程： 分析问题设计算法编写程序整理结果程序设计研究的四个层次： 算法方法学语言工具理由2：提高分析问题的能力 算法的形式化思维的逻辑性、条理性9算法算法应用应用 人类基因数据库分析 因
3、特网信息管理 电子商务：加密/解密，保护隐私 火车、航班调度 大科学计算 应用软件 实际应用。10算法算法可以看做一项技术可以看做一项技术算法可以看作是一项技术例 对于排序问题（问题规模：n=106） 插入排序算法：复杂度c1n2合并排序算法：复杂度c2nlog2n计算机A每秒能执行10亿条指令计算机B每秒能执行1000万条指令计算机A+插入排序算法(c1=2)，则计算机A花的时间为：计算机B+合并排序算法(c2=50)，则计算机B花的时间为：111.1.2 算法及其重要性质算法及其重要性质算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入输入：有外部提供的量
4、作为算法的输入。(2)输出输出：算法产生至少一个量作为输出。(3)确定性确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。12欧几里德算法mnr例：欧几里德算法辗转相除法求两个自然数 m 和 n 的最大公约数13算法与程序的区别算法与程序的区别程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。141.1.3 算法
5、的描述方法算法的描述方法 自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段15欧几里德算法 输入m 和n； 求m除以n的余数r； 若r等于0，则n为最大公约数，算法结束；否则执行第步； 将n的值放在m中，将r的值放在n中； 重新执行第步。16 流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次17开始输入m和nr=m % nr=0Nm=n；n=r输出n结束Y欧几里德算法18 程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数19#include int C
6、ommonFactor(int m, int n)int r=m % n;while (r!=0)m=n;n=r;r=m % n;return n;void main( )coutCommonFactor(63, 54)0，存在正数和n0 0使得对所有n n0有：0 f(n)cg(n) 等价于 f(n) / g(n) 0 ，as n。30（4）紧渐近界记号紧渐近界记号 (g(n) = f(n) | 存在正常数c1,c2和n0使得对所有n n0有：c1g(n) f(n) c2g(n) 定理定理1： (g(n) = O (g(n) (g(n) 31渐近分析记号在等式和不等式中的意义渐近分析记号在等
7、式和不等式中的意义f(n)= (g(n)的确切意义是：f(n) (g(n)。一般情况下，等式和不等式中的渐近记号(g(n)表示(g(n)中的某个函数。例如：2n2 + 3n + 1 = 2n2 + (n) 表示 2n2 +3n +1=2n2 + f(n)，其中f(n) 是(n)中某个函数。等式和不等式中渐近记号O,o, 的意义是类似的。32渐近分析中函数比较渐近分析中函数比较f(n)= O(g(n) a b;f(n)= (g(n) a b;f(n)= (g(n) a = b;f(n)= o(g(n) a b;33渐近分析记号的若干性质渐近分析记号的若干性质（1）传递性：）传递性：f(n)= (
8、g(n)， g(n)= (h(n) f(n)= (h(n)；f(n)= O(g(n)， g(n)= O (h(n) f(n)= O (h(n)；f(n)= (g(n)， g(n)= (h(n) f(n)= (h(n)；f(n)= o(g(n)， g(n)= o(h(n) f(n)= o(h(n)；34（2）反身性：）反身性：f(n)= (f(n)；f(n)= O(f(n)；f(n)= (f(n).（3）对称性：）对称性：f(n)= (g(n) g(n)= (f(n) .（4）互对称性：）互对称性：f(n)= O(g(n) g(n)= (f(n) ；35（5）算术运算：）算术运算：O(f(n)+
9、O(g(n) = O(maxf(n),g(n) ；O(f(n)+O(g(n) = O(f(n)+g(n) ；O(f(n)*O(g(n) = O(f(n)*g(n) ；O(cf(n) = O(f(n) ；g(n)= O(f(n) O(f(n)+O(g(n) = O(f(n) 。36算法分析中常见的复杂性函数算法分析中常见的复杂性函数 凡渐近时间复杂度有多项式时间限界的算法称做多项式时间算法(polynomial time algorithm)，而渐近时间复杂度为指数函数限界的算法称做指数时间算法（exponential time algorithm）。37算法分析中常见的复杂性函数算法分析中常见
10、的复杂性函数38最常见的多项式时间算法的渐近时间复杂度 O(1)O(log n)O(n)O(nlog n)O(n2)O(n3)最常见的指数时间算法的渐近时间复杂度 O(2n)O(n！)O(nn)算法分析中常见的复杂性函数算法分析中常见的复杂性函数39小规模数据小规模数据40中等规模数据中等规模数据411.2.3 非递归算法的分析非递归算法的分析算法算法非递归算法、递归算法非递归算法、递归算法例：顺序搜索算法例：顺序搜索算法templateint seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; re
11、turn -1;42非递归算法分析的一般步骤：非递归算法分析的一般步骤：1. 决定用哪个（或哪些）参数作为算法问题规模的度量2. 找出算法中的基本语句3. 检查基本语句的执行次数是否只依赖于问题规模4. 建立基本语句执行次数的求和表达式5. 用渐进符号表示这个求和表达式关键：建立一个代表算法运行时间的求和表达式，关键：建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。然后用渐进符号表示这个求和表达式。43（1）Tmax(n) = max T(I) | size(I)=n =O(n)（2）Tmin(n) = min T(I) | size(I)=n =O(1)（3）在平均情
12、况下，假设： (a) 搜索成功的概率为p ( 0 p 1 )； (b) 在数组的每个位置i ( 0 i n )搜索成功的概率相同，均为 p/n。44templatevoid insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 & ajkey ) / c4 sum of ti aj+1=aj; / c5 sum of (ti-1) j-; / c6 sum og (ti-1) aj+1=key; / c7 n-1 45在最好情况下，ti=1, for 1 i n;在最坏情况下，ti i+1, for
13、 1 i n;46对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort 达到其最坏情形。因此，由此可见，Tmax(n)= (n2)471.2.4 递归算法的分析递归算法的分析关键：关键： 根据递归过程建立递推关系式，然后求解根据递归过程建立递推关系式，然后求解这个递推关系式。这个递推关系式。1. 猜测技术猜测技术: 对递推关系式估计一个上限，然后对递推关系式估计一个上限，然后（用数学归纳法）证明它正确。（用数学归纳法）证明它正确。482. 扩展递归技术493. 通用分治递推式大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问
14、题的解需要的工作量。50递归算法复杂性分析int factorial(int n)if (n = 0) return 1;return n*factorial(n-1);51最优算法最优算法问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。堆排序算法是最优算法。52算法的后验分析（Posteriori）也称算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对应的程序并上机运行。1.2.5 算法的后验分析算法的后验分析53一般步骤：1. 明确实验目的2. 决
15、定度量算法效率的方法，为实验准备算法的程序实现3. 决定输入样本，生成实验数据4. 对输入样本运行算法对应的程序，记录得到的实验数据5. 分析得到的实验数据54将将能能在在多多项项式式时时间间求求解解的的问问题题看看作作易易处处理理问问题题(tractable problem)，而而将将至至今今尚尚未未找找到到多多项项式式时时 间间 算算 法法 求求 解解 的的 问问 题题 视视 为为 难难 处处 理理 问问 题题(intractable problem)。 1.3 NP完全性理论完全性理论55P类和类和NP类问题类问题(P类类和和NP类类) P是是所所有有可可在在多多项项式式时时间间内内用用
16、确确定定算算法法求求解解的的判判定定问问题题的的集集合合。NP是是所所有有可可在在多多项项式式时时间内用不确定算法求解的判定问题的集合。间内用不确定算法求解的判定问题的集合。(多多项项式式约约化化) 令令Q1和和Q2是是两两个个问问题题，如如果果存存在在一一个个确确定定算算法法A求求解解Q1，而而算算法法A以以多多项项式式时时间间调调用用另另一一个个求求解解Q2的的确确定定算算法法B。若若不不计计B的的工工作作量量，算算法法A是是多多项项式式时时间间的的，则则称称Q1约约化化（reduced to）为为Q2，记做记做QQ1 1QQ2 2。56NP难度和难度和NP完全问题完全问题（NP难难度度）
17、对对于于问问题题Q以以及及任任意意问问题题Q1 NP，都都有有Q1Q，则称则称Q是是NP难度难度（NP hard）的。的。（NP完完全全）对对于于问问题题Q NP，Q是是NP难难度度的的，则则称称Q是是NPC（NP complete）的。的。57如如何何确确定定某某个个问问题题Q是是否否是是NP难难度度的的？一一般般的的证证明明策略由以下两步组成：策略由以下两步组成：（1）选择一个已经证明是）选择一个已经证明是NP难度问题难度问题Q1；（2）求证求证Q1Q。由由于于Q1是是NP难难度度的的，因因此此所所有有NP类类问问题题都都可可约约化化到到Q1，根根据据约约化化的的传传递递性性，任任何何NP
18、类类问问题题都都可可约约化化到到Q，所以所以Q是是NP难度的。难度的。如如果果进进一一步步表表明明Q本本身身是是NP类类的的，则则问问题题Q是是NPC的。的。58PNP？目前人们猜测PNP，则P类问题、NP类问题、NP完全问题之间的关系如下：59一些典型的一些典型的NPC问题问题1SAT 问题（问题（Boolean Satisfiability Problem）2最大团问题（最大团问题（Maximum Clique Problem）3图着色问题（图着色问题（Graph Coloring Problem ）4. 哈密顿回路问题（哈密顿回路问题（Hamiltonian Cycle Problem）5TSP 问题（问题（Traveling Salsman Problem）6顶点覆盖问题（顶点覆盖问题（Vertex Cover Problem）7最长路径问题（最长路径问题（Longest Path Problem ）8子集和问题（子集和问题（Sum of Subset Problem）60
