计算机算法学习课件.ppt

计算机算法分析 杨鹏 简介 教材《算法设计、分析与实现： C、C++和Java》 理论教学学时：40；实践教学学时：20 教学目的：使学生掌握算法分析与设计的基本理论，掌握算法设计的一般方法，会使用分治法、贪心法、动态规划法、回溯法、分支限界法等设计算法，培养学生科学的思维方法和解决实际问题的基本能力。 今天计算机这么快，算法还重要吗 ? 虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量。在网络时代，越来越多的挑战需要靠卓越的算法来解决。 第一章 渐增型算法 算法设计与分析 什么是算法 算法分析的基本概念 伪代码与程序设计语言的区别 伪代码描述着眼于算法思想的阐述，高度抽象； 伪代码描述，不关心数据的存储格式； 伪代码描述无需对变量实现声明。 算法的JAVA描述 【参数与返回值】欲排序的序列A 【数据设置】过程访问的变量包括两重嵌套循环的控制变量j和i，暂存变量key。 【关键代码】序列长度，序列元素下标。 渐增算法思路 把A[p...q]和A[q+1...r]复制到序列L[1…n1]和R[1…n2]； 【数据设置】过程访问的三个变量i、j、k， i、j初始化为1，k初始化为p 比较L[i]和R[j] ，将较小者复制到A[k],直到L和R被扫描完。 算法的运行时间 假设A[k]含有n(n=r-p+1)个元素。第4~5行，以及第6~7行的for循环均重复n次。此外，第12~17行的while循环重复k-p次，第18~21行的while循环重复r-p+1次，两者一共耗时Θ(n)，所以算法最坏情况时间为Θ(n)。 算法的JAVA描述 【参数与返回值】序列A[p,…,r]中有序子序列A[p,…,q]和A[q,…,r] 【数据设置】两个辅助序列L和R。表示子序列起止下标的p、q、r。 【关键代码】 算法思路 对序列A[p…r]进行原地重组 选择元素x= A[r]作为主元素，以它为分界点对序列A[p…r]划分。分为前后两段A[p…q]和A[q+1…r]，使得A[p…q]的元素都不超过x， A[q+1…r]的元素都大于x。 维护两个下标i，j。初始时，分别为p-1和p。j在[p…r]中扫描，若A[j]= A[r]则A[j]和 A[i+1]交换；然后i+1 随着j的增加A [p…i]和A [i+1…j]也随之增长，最终j达到r-1. 1.4 序列的划分 1．问题的理解与描述 序列的划分问题描述如下： 输入：序列A[p…r]。 输出：下标q（p? q ? r），原序列A[p…r]的一个重排：使得A[p…q]中的元素值不超过A[q](=原A[r]的值)，而A[q+1...r]中的元素值均大于A[q]。 * 算法:是指解决一个具体问题的意义明确的步骤的集合。 概括地说，算法是指解题方案的准确而完整的描述。从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。 算法概念 * 算法概念 输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 是满足下述性质的指令序列。 算法： 对于同一个问题可以有不同的解题方法和步骤，也就是有不同的算法。算法有优劣，一般而言，应当选择简单的、运算步骤少的，既运算快、内存开销小的算法（算法的时空效率）。 算法概念 * 算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量， 需要时间资源的量称为时间复杂性，需要的空间资源的 量称为空间复杂性。这个量应该只依赖于算法要解的问 题的规模、算法的输入和算法本身的函数。 算法运行时间的3种情形 对固定的输入规模，使运算时间最长的输入所消耗的运行时间称为算法的最坏情形时间。 对固定的输入规模，使运行时间最短的输入所消耗的时间，称为最好情形时间。 假定固定的输入规模为n，所有不同输入构成的集合为Dn，对问题的每一个输入为I?Dn，若已知该输入发生的概率为P(I)，对应的运行时间为T(I)，运行时间的数学期望值 称为算法的平均情形时间。 实例 在线性表A中查找。（a）查找值为x=1的元素，从A[1]起依次要进行5次检测，第一次找到值为1的元素。（b）查找值为x=11的元素，从A[1]起依次检测完所有元素（进行10次检测），没有找到值为11的元素—