《《算法设计与分析》ppt课件》由会员分享，可在线阅读，更多相关《《算法设计与分析》ppt课件（356页珍藏版）》请在金锄头文库上搜索。
1、.,1,中国计算机学会“21世纪大学本科计算机专业系列教材”算法设计与分析,王晓东编著,.,2,主要内容介绍,第1章算法引论 第2章递归与分治策略 第3章动态规划 第4章贪心算法 第5章回溯法 第6章分支限界法,.,3,主要内容介绍（续）,第7章概率算法 第8章NP完全性理论 第9章近似算法 第10章算法优化策略,.,4,第1章 算法引论,1.1算法与程序 1.2表达算法的抽象机制 1.3描述算法 1.4算法复杂性分析,本章主要知识点：,.,5,1.1算法与程序,输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：
2、算法中每条指令的执行次数有限，执行每条指令的时间也有限。,是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。,是满足下述性质的指令序列。,算法：,程序：,.,6,1.从机器语言到高级语言的抽象,1.2表达算法的抽象机制,高级程序设计语言的主要好处是：,（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。,（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；,（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好
3、，可维护性强，可靠性高；,（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；,.,7,2.抽象数据类型,1.2表达算法的抽象机制,抽象数据类型是算法的一个数据模型连同定义在该模型上 并作为算法构件的一组运算。,抽象数据类型带给算法设计的好处有：,（1）算法顶层设计与底层实现分离； （2）算法设计与数据结构设计隔开，允许数据结构自由选择； （3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； （4）用抽象数据类型表述的算法具有很好的可维护性； （5）算法自然呈现模块化； （6）为自顶向下逐步求精和模块化提供有效途径和工具； （7
4、）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。,.,8,在本书中，采用Java语言描述算法。 1.Java程序结构,1.3描述算法,以下，对Java语言的若干重要特性作简要概述。,（1）Java程序的两种类型：应用程序和applet 区别：应用程序的主方法为main，其可在命令行中用命令 语句 java 应用程序名 来执行； applet的主方法为init，其必须嵌入HTML文件，由 Web浏览器或applet阅读器来执行。,（2）包：java程序和类可以包(packages)的形式组织管理。,（3）import语句：在java程序中可用import语句加载所需的包。 例如，i
5、mport java.io.*;语句加载java.io包。,.,9,1.3描述算法,2.Java数据类型,Java对两种数据类型的不同处理方式：,s = new String(“Welcome”); String s = new String(“Welcome”);,.,10,1.3描述算法,表格1-1 Java基本数据类型,.,11,1.3描述算法,3.方法,在Java中，执行特定任务的函数或过程统称为方法(methods) 。 例如，java的Math类给出的常见数学计算的方法如下表所示：,.,12,1.3描述算法,3.方法,计算表达式 值的自定义方法ab描述如下：,public stat
6、ic 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)/2.0; ,.,13,1.3描述算法,4.异常,Java的异常提供了一种处理错误的方法。当程序发现一个错误，就引发一个异常，以便在合适地方
7、捕获异常并进行处理。,通常用try块来定义异常处理。每个异常处理由一个catch语句组成。,public static void main(String args) try f ( ); catch (exception1) 异常处理; catch (exception2) 异常处理; finally finally块; ,.,14,1.3描述算法,5.Java的类,(4)访问修饰,Java的类一般由4个部分组成：,(1)类名,(2)数据成员,(3)方法,.,15,1.3描述算法,6.通用方法,下面的方法swap用于交换一维整型数组a的位置i和位置j处的值。,public static voi
8、d 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; ,该方法只适用于 整型数组,该方法具有通用性，适用于Object类型及其所有子类,以上方法修改如下：,.,16,1.3描述算法,6.通用方法,（1）Computable界面,public static Computable sum(Computable a, int n) if (a.length
9、= 0) return null; Computable sum = (Computable) a0.zero(); for (int i = 0; i n; i+) sum.increment(ai); return sum; ,利用此界面使 方法sum通用化,.,17,1.3描述算法,6.通用方法,（2）java.lang.Comparable 界面,Java的Comparable 界面中惟一的方法头compareTo用于比较 2个元素的大小。例如java.lang.CpareTo(y) 返回x-y的符号，当xy时返 回正数。,（3）Operable 界面,有些通用方法同时需要Comput
10、able界面和Comparable 界面 的支持。为此可定义Operable界面如下:,public interface Operable extends Computable, Comparable ,（4）自定义包装类,由于Java的包装类如Integer等已定义为final型，因此无法 定义其子类，作进一步扩充。为了需要可自定义包装类。,.,18,1.3描述算法,7.垃圾收集 8.递归,Java的new运算用于分配所需的内存空间。 例如， int a = new int500000; 分配2000000字节空间 给整型数组a。频繁用new分配空间可能会耗尽内存。Java的垃 圾收集器会适
11、时扫描内存，回收不用的空间（垃圾）给new重新 分配。,Java允许方法调用其自身。这类方法称为递归方法。,public static int sum(int a, int n) if (n=0) return 0; else return an-1+sum(a,n-1); ,计算一维整型数组前n个元素之和的递归方法,.,19,1.4算法复杂性分析,算法复杂性是算法运行所需要的计算机资源的量， 需要时间资源的量称为时间复杂性，需要的空间资源的 量称为空间复杂性。这个量应该只依赖于算法要解的问 题的规模、算法的输入和算法本身的函数。如果分别用 N、I和A表示算法要解问题的规模、算法的输入和算法
12、本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。 一般把时间复杂性和空间复杂性分开，并分别用T和S来 表示，则有： T=T(N,I)和S=S(N,I) 。 （通常，让A隐含在复杂性函数名当中）,.,20,1.4算法复杂性分析,最坏情况下的时间复杂性：,最好情况下的时间复杂性：,平均情况下的时间复杂性：,其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*) 达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法 输入；而P(I)是在算法的应用中出现输入I的概率。,.,21,1.4算法复杂性分析,算法复杂性在渐近意义下的阶：,渐近意义下的记号：O、o
13、设f(N)和g(N)是定义在正数集上的正函数。,O的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)。即f(N)的阶不高于g(N)的阶。,根据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)，则O(f)+O(g)=O(f)； (5)O(Cf(N)=O(f(N)，其中C是一个正的常数； (6)f=O(f)。,.,22,1.4算法复杂性
14、分析,的定义：如果存在正的常数C和自然数N0，使得当NN0时 有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它 的一个下界，记为f(N)=(g(N)。即f(N)的阶不低于g(N)的阶。,的定义：定义f(N)= (g(N)当且仅当f(N)=O(g(N)且 f(N)= (g(N)。此时称f(N)与g(N)同阶。,o的定义：对于任意给定的0，都存在正整数N0，使得 当NN0时有f(N)/Cg(N),则称函数f(N)当N充分大时的阶比 g(N)低，记为f(N)=o(g(N)。 例如，4NlogN+7=o(3N2+4NlogN+7)。,.,23,第2章 递归与分治策略,.,24,
15、将要求解的较大规模的问题分割成k个更小规模的子问题。,算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,.,25,算法总体思想,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,.,26,算法总体思想,将求出的小规模的问题的解合并为一个
16、更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,.,27,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。 凡治众如治寡，分数是也。 -孙子兵法,.,28,2.1 递归的概念,直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,下面来看几个实例。,.,29,2.1 递归的概念,例1 阶乘函数 阶乘函数可递归地定义为：,
