算法设计与分析

1、算法设计与分析林林劼劼emailemail：phonehone程介绍n学时：40学时+8实验n考试方式：考试 成绩：20%中期考试+10%平时+70%期末n教材： 王晓东，算法设计与分析（第二版），清华大学出版社；n参考资料：1张德富 ，算法设计与分析 ，国防工业出版社； 2Michael T. Goodrich ，算法分析与设计 ，人民邮电出版社 。3 Kleinberg 等 ,算法导论,清华大学出版社主要内容介绍n第1章算法引论n第2章递归与分治策略n第3章动态规划n第4章贪心算法n第5章回溯法n第6章分支限界法主要内容介绍（续）n第7章

2、概率算法第8章NP完全性理论第9章近似算法第10章 算法优化策略第1章 算法引论n1.1 算法与程序n1.2 表达算法的抽象机制n1.3 描述算法n1.4 算法复杂性分析本章主要知识点：1.1算法与程序n输 入：有零个或多个外部量作为算法的输入。 n输 出：算法产生至少一个量作为输出。 n确定性：组成算法的每条指令清晰、无歧义。 n有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 是满足下述性质的指令序列。算法：程序：1.从机器语言到高级语言的抽象1.2表达算法的抽象机制高级程序设计语言的主要好处是：

3、（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；1.对明确数学问题的算法设计1.2表达算法的抽象机制选用该问题的一个数学模型-在已知条件下的初始状态、结束状态和状态关系-从已知状态到达结束状态的运算步骤-形成算

4、法为了将两层运算隔开，使二者在设计时不互相影响必须对二者的接口进行抽象。让底层通过接口为顶层服务，顶层通过接口调用底层运算。这个接口就是抽象数据类型(abstract data types,ADT)顶层运算步骤顶层运算步骤底层运算步骤底层运算步骤自顶向下数据模型级数据结构级2.抽象数据类型1.2表达算法的抽象机制 抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有： （1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用

5、抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 在本书中，采用Java语言描述算法。1.Java1.Java程序结构程序结构 1.3描述算法以下，对JavaJava语言的若干重要特性作简要概述。 （1）Java程序的两种类型：应用程序和appletapplet区别：应用程序的主方法为main，其可在命令行中用命令语句 java 应用程序名 来执行；applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行。（2）包：j

6、ava程序和类可以用包(packages)的形式组织管理。 （3）import语句：在java程序中可用import语句加载所需的包。例如，import java.io.*;语句加载java.io包。 1.3描述算法2.Java2.Java数据类型数据类型数据类型 基本数据类型：详见下页表1-1 非基本数据类型：如 Byte, Integer, Boolean, String等。 Java对两种数据类型的不同处理方式： 对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）。如:int k;对非基本数据类型：语句 String s; 并不建立具有数据类型Str

7、ing的对象，而是建立一个类型String的引用对象，数据类型为String的对象可用下面的new语句建立。 s = new StringString(“Welcome”);StringString s = new StringString(“Welcome”);1.3描述算法表格表格1-1 Java1-1 Java基本数据类型基本数据类型类型缺省值分配空间（bits）取值范围booleanfalse1true,falsebyte08-128,127charu000016u0000,uFFFFdouble0.0644.9*10-324 1.8*10308float0.0321.4*10-45

8、3.4*1038int032-2147483648,2147483647long0649.2*1017short016-32768,327671.3描述算法3.3.方法方法在Java中，执行特定任务的函数或过程统称为方法(methods) 。例如，java的MathMath类类给出的常见数学计算的方法如下表所示：方法方法功能功能方法方法功能功能abs(x)x的绝对值max(x,y)x和y中较大者ceil(x)不小于x的最小整数min(x,y)x和y中较小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整数sqrt(x)x的平方根log

9、(x)x的自然对数tan(x)x的正切1.3描述算法3.3.方法方法 2baba计算表达式 值的自定义方法ab描述如下： public static int ab(int a, int b) return (a+b+Math.abs(a-b)/2; （1）方法参数：Java中所有方法的参数均为值参数。上述方法ab中，a和b是形式参数，在调用方法时通过实际参数赋值。 （2）方法重载：Java允许方法重载，即允许定义有不同签名的同名方法。上述方法ab可重载为： public static double ab(double a, double b) return (a+b+Math.abs(a-b)

10、/2.0; 1.3描述算法4.4.异常异常 Java的异常提供了一种处理错误的方法。当程序发现一个错误，就引发一个异常，以便在合适地方捕获异常并进行处理。 通常用trytry块来定义异常处理。每个异常处理由一个catchcatch语句组成。 public static void main(String args) try f ( ); catch (exception1) 异常处理; catch (exception2) 异常处理; finally finally块; 1.3 描述算法5.Java5.Java的类（的类（抽象数据类型抽象数据类型）(4)访问修饰访问修饰公有(public) 私有

11、(private)保护(protected) Java的类一般由4个部分组成：(1)类名类名(2)数据成员数据成员(3)方法方法public class rectangle public static final int MAX=2000;private int x,y,h,w; /x,y是矩形的左下角坐标，是矩形的左下角坐标，h,w是高和宽是高和宽public Rectangle()this（0,0,0,0）;public int getHeight()return h;public int getWidth()return w;public static void main(String

12、args)Rectangle r=newRectangle();System.out.print(“r.h=“+r.getHeight()+”r.w=“+r.getWidth();1.3 描述算法5.Java5.Java的类（的类（抽象数据类型抽象数据类型）(1)类的对象：声明和创建方法类似于变量的声明；对对象类的对象：声明和创建方法类似于变量的声明；对对象和成员的访问可用和成员的访问可用”.”.”(2)构造方法：用于初始化对象的数据成员，构造方法名与它构造方法：用于初始化对象的数据成员，构造方法名与它所在的类名相同。公有方法，不能有返回值和类型。所在的类名相同。公有方法，不能有返回值和类型。

13、(3)静态类成员：静态类成员：staticstatic表示，仅维护一个拷贝表示，仅维护一个拷贝1.3描述算法6.6.通用方法通用方法 下面的方法swapswap用于交换一维整型数组a的位置i和位置j处的值。 public static void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp; public static void swap(object a, int i, int j) object temp = ai; ai = aj; aj = temp; 该方法只适用于该方法只适用于整型数组整型数组该方法具有通用性

14、，适用该方法具有通用性，适用于于ObjectObject类型及其所有子类型及其所有子类类 以上方法修改如下：以上方法修改如下：1.3描述算法6.6.通用方法通用方法 （1 1）ComputableComputable界面界面 public static Computable sum(Computable a, int n) if (a.length = 0) return null; Computable sum = (Computable) a0.zero(); for (int i = 0; i n; i+) sum.increment(ai); return sum;利用此界面使利用此界

15、面使方法方法sumsum通用化通用化 1.3描述算法6.6.通用方法通用方法 （2 2）java.lang.Comparable java.lang.Comparable 界面界面 Java的Comparable 界面中惟一的方法头compareTo用于比较2个元素的大小。例如java.lang.CpareTo(y)返回x-y的符号，当xy时返回正数。（3 3）OperableOperable 界面界面 有些通用方法同时需要Computable界面和Comparable 界面的支持。为此可定义Operable界面如下:public interface Operable extends Comp

16、utable, Comparable （4 4）自定义包装类）自定义包装类 由于Java的包装类如Integer等已定义为final型，因此无法定义其子类，作进一步扩充。为了需要可自定义包装类。 1.3 描述算法7.7.垃圾收集垃圾收集8.8.递归递归Java的newnew运算用于分配所需的内存空间。例如， int a = new int500000; 分配2000000字节空间给整型数组a。频繁用new分配空间可能会耗尽内存。Java的垃垃圾收集器圾收集器会适时扫描内存，回收不用的空间（垃圾）给new重新分配。 Java允许方法调用其自身。这类方法称为递归方法。public static i

17、nt sum(int a, int n) if (n=0) return 0; else return an-1+sum(a,n-1); 计算一维整型数组前计算一维整型数组前n n个个元素之和的递归方法元素之和的递归方法 1.4算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性时间复杂性，需要的空间资源的量称为空间复杂性空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分

18、别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。（通常，让A隐含在复杂性函数名当中） 1.4算法复杂性分析主要问题：如何将复杂性函数具体化？根据T（N,I)的概念，它应该是算法在一台抽象的计算机上运行所需要的时间。u设此抽象的计算机所提供的元运算有k种，分别记为O1，O2,Oku又设每次执行一次这些元运算的时间分别为t1,.tku对于算法A，设统计用到元运算Oi的次数为ei ei=ei(N,I) 因此kiiiINetINT1),(),(1.4算法复杂性分析最坏情况下的时间复杂性：),(maxmaxINT(N)TNDI),(max1INetkiiiDIN),(*1INetkiii),(*INT最好情况下的时间复杂性：),(minminINT(N)TNDI),(min1INetkiiiDIN),(1INetkiii),(INT平均情况下的时间复杂性：NDIINTIP(N)T),()(avgNDIkiiiINetIP),()(1 其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。II1.4算法复杂性分析)(NT复杂性渐近性态：当N单调增加趋于 时，T（N）也单调增加趋于 如果存在 当N- 时有