算法分析与设计第1章详解

算法设计与分析福州高校数计(软件)学院陈家瑞jrchen@1261课程支配总学时：32考查方式：闭卷考试(80%)+出勤作业(20%)2教材计算机算法设计与分析（第4版）王晓东编著电子工业出版社3参考书1算法设计与分析-C++语言描述(第2版)陈慧南编著电子工业出版社4参考书2算法导论(原书第3版)ThomasH.Cormen等著,殷建平等译机械工业出版社5课程主要内容

第1章算法概述第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第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算法应用™人类基因数据库分析因特网信息管理™电子商务：加密/解密，爱护隐私™火车、航班调度™大科学计算™应用软件™实际应用。。。10算法可以看做一项技术™算法可以看作是一项技术例对于排序问题（问题规模：n=106）插入排序算法：困难度c1n2合并排序算法：困难度c2nlog2n计算机A每秒能执行10亿条指令计算机B每秒能执行1000万条指令计算机A+插入排序算法(c1=2)，则计算机A花的时间为：计算机B+合并排序算法(c2=50)，则计算机B花的时间为：111.1.2算法及其重要性质算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部供应的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。12欧几里德算法mnr例：欧几里德算法——辗转相除法求两个自然数m和n的最大公约数13 算法与程序的区分程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。14 1.1.3算法的描述方法⑴自然语言优点：简洁理解缺点：冗长、二义性运用方法：粗线条描述算法思想留意事项：避开写成自然段15欧几里德算法①输入m和n；②求m除以n的余数r；③若r等于0，则n为最大公约数，算法结束； 否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。16⑵流程图优点：流程直观缺点：缺少严密性、敏捷性运用方法：描述简洁算法留意事项：留意抽象层次17起先输入m和n r=m%n

r=0

Nm=n；n=r 输出n结束Y欧几里德算法18⑶程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高运用方法：算法须要验证留意事项：将算法写成子函数19#include<iostream.h>intCommonFactor(intm,intn){ intr=m%n; while(r!=0) { m=n; n=r; r=m%n; } returnn;}voidmain(){ cout<<CommonFactor(63,54)<<endl;}

欧 几 里 德 算 法20⑷伪代码——算法语言伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它接受某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达实力强，抽象性强，简洁理解21欧几里德算法 1.r=m%n; 2.循环直到r等于0 2.1m=n; 2.2n=r; 2.3r=m%n; 3.输出n;221.1.4问题求解的一般过程证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法23

1.查找问题

2.排序问题

3.图问题

4.组合问题

5.几何问题1.1.5重要的问题类型241.2算法分析1.2.1最好、最坏和平均状况1.2.2渐近符号1.2.3非递归算法的分析1.2.4递归算法的分析1.2.5算法的试验分析25算法困难性分析算法困难性=算法所须要的计算机资源算法的时间困难性T(n)；算法的空间困难性S(n)。其中n是问题的规模（输入大小）。26算法的时间困难性（1）最坏状况下的时间困难性Tmax(n)=max{T(I)|size(I)=n}（2）最好状况下的时间困难性Tmin(n)=min{T(I)|size(I)=n}（3）平均状况下的时间困难性Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。27算法渐近困难性T(n),asn;(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的渐近性态，为算法的渐近困难性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简洁。28渐近分析的记号在下面的探讨中，对全部n，f(n)0，g(n)0。（1）渐近上界记号OO(g(n))={f(n)|存在正常数c和n0使得对全部nn0有：0f(n)cg(n)}（2）渐近下界记号(g(n))={f(n)|存在正常数c和n0使得对全部nn0有：0cg(n)f(n)}29（3）非紧上界记号oo(g(n))={f(n)|对于任何正常数c>0，存在正数和n0>0使得对全部nn0有：0f(n)<cg(n)}等价于f(n)/g(n)0，asn。30（4）紧渐近界记号(g(n))={f(n)|存在正常数c1,c2和n0使得对全部nn0有：c1g(n)f(n)c2g(n)}定理1：(g(n))=O(g(n))(g(n))31渐近分析记号在等式和不等式中的意义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))ab;f(n)=(g(n))ab;f(n)=(g(n))a=b;f(n)=o(g(n))a<b;33渐近分析记号的若干性质（1）传递性：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))；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))+O(g(n))=

O(max{f(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算法分析中常见的困难性函数凡渐近时间困难度有多项式时间限界的算法称做多项式时间算法(polynomialtimealgorithm)，而渐近时间困难度为指数函数限界的算法称做指数时间算法（exponentialtimealgorithm）。37算法分析中常见的困难性函数38最常见的多项式时间算法的渐近时间困难度O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n2)＜O(n3)最常见的指数时间算法的渐近时间困难度O(2n)＜O(n！)＜O(nn)算法分析中常见的困难性函数39小规模数据40中等规模数据411.2.3非递归算法的分析算法——非递归算法、递归算法例：依次搜寻算法template<classType>intseqSearch(Type*a,intn,Typek){for(inti=0;i<n;i++) if(a[i]==k)returni;return-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）在平均状况下，假设：(a)搜寻成功的概率为p(0p1)；(b)在数组的每个位置i(0i<n)搜寻成功的概率相同，均为p/n。44template<classType>voidinsertion_sort(Type*a,intn){Typekey;//costtimesfor(inti=1;i<n;i++){//c1n

key=a[i];//c2n-1

intj=i-1;//c3n-1

while(j>=0&&a[j]>key){//c4sumofti a[j+1]=a[j];//c5sumof(ti-1)

j--;//c6sumog(ti-1) }a[j+1]=key;//c7n-1

}}45在最好状况下，ti=1,for1i<n;在最坏状况下，tii+1,for1i<n;46对于输入数据a[i]=n-i,i=0,1,…,n-1，算法insertion_sort达到其最坏情形。因此，由此可见，Tmax(n)=(n2)471.2.4递归算法的分析关键：™依据递归过程建立递推关系式，然后求解这个递推关系式。1.揣测技术:对递推关系式估计一个上限，然后（用数学归纳法）证明它正确。482.扩展递归技术49 3.通用分治递推式大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题须要求解，而cnk是合并各个子问题的解须要的工作量。50递归算法困难性分析intfactorial(intn){ if(n==0)return1; returnn*factorial(n-1); }

51最优算法问题的计算时间下界为(f(n))，则计算时间困难性为O(f(n))的算法是最优算法。例如，排序问题的计算时间下界为(nlogn)，计算时间困难性为O(nlogn)的排序算法是最优算法。堆排序算法是最优算法。52 算法的后验分析（Posteriori）也称算法的试验分析，它是一种事后计算的方法，通常须要将算法转换为对应的程序并上机运行。 1.2.5算法的后验分析53一般步骤：1.明确试验目的2.确定度量算法效率的方法，为试验准备算法的 程序实现3.确定输入样本，生成试验数据4.对输入样本运行算法对应的程序，记录得到的 试验数据5.分析得到的试验数据54将能在多项式时间求解的问题看作易处理问题(tractableproblem)，而将至今尚未找到多项式时间算法求解的问题视犯难处理问题(intractableproblem)。1.3NP完全性理论55P类和NP类问题(P类和NP类)P是全部可在多项式时间内用确定算法求解的判定问题的集合。NP是全部可在多项式时间内用不确定算法求