算法分析与设计课件.pptx

《算法分析与设计课件.pptx》由会员分享，可在线阅读，更多相关《算法分析与设计课件.pptx（71页珍藏版）》请在三一办公上搜索。

1、1,算法分析与设计,2,第1章 算法引论,1课程学习背景 1.1 为什么学习算法？1.2 算法的定义1.3 如何描述一个算法？2算法复杂性分析2.1 计算模型与算法分析框架2.2 渐进表示,为什么要学习算法,算法是计算机科学的基石，是改造世界的有力工具！ 互联网是20世纪最伟大的发明之一，改变了世界，改变了我们的生活！各种算法在支撑着整个互联网的正常运行，互联网的信息传输需要路由选择算法，互联网的信息安全需要加密算法，互联网的信息检索需要模式匹配算法，互联网的信息存储需要排序算法，没有算法也就没有互联网！学习算法可以开发人们的分析能力 算法是解决问题的一类特殊方法，它是经过对问题的准确理解和定

2、义获取答案的过程。是你获得高薪职位的敲门砖！,3,“微积分以及在微积分基础上建立起来的数学分析体系成就了现代科学，而算法则成就了现代世界” David Berlinski, 2000,思考题：小鸡啄米,输入：一个m*n的矩阵A，矩阵的每一个元素都是一个非负整数，代表该位置的米数；有一只小鸡从左上角A11出发，每次往右或者往下走一步，走到右下角Amn停止；小鸡会将途中经过的所有米粒都吃掉；设计一个算法，计算出小鸡应该如何走保证吃到的米粒最多。分析算法时间复杂度。,4,思考题：小鸡啄米,假设有两只小鸡从左上角A11出发，都要走到右下角Amn，都只能向下或者向右移动；两只小鸡移动的先后顺序不做限制，

3、但是先到某个位置的小鸡会将该位置米粒吃完；问如何安排两只小鸡的移动顺序与轨迹，使得两只小鸡吃到的米粒数之和最多？如果有k只小鸡呢？,5,6,为什么要分析算法效率？,写程序比效率更重要的因素可复用性、界面友好度、可扩展性、易读性、安全性。效率是可不可行的判断标准指数级算法 vs. 多项式时间算法 . ( 2 )效率就是金钱Java vs. C,7,算法效率的各个方面,时间效率排序算法效率空间效率路由器与布隆过滤器（bloom filter）通讯量效率比特币与稀疏恢复MapReduce与DSP模型,8,第1章 算法引论,1课程学习背景 1.1 为什么学习算法？1.2 算法的定义1.3 如何描述一个

4、算法？2算法复杂性分析2.1 计算模型与算法分析框架2.2 渐进表示,什么是算法？,简单说来，算法就是问题的程序化解决方案。定义：算法就是一个定义良好的可计算过程，它取一个或者一组值作为输入，并产生出一个或者一组值作为输出。即，算法就是一系列的计算步骤，用来将输入数据转换成输出结果。,“冒泡”排序是个计算过程,9,什么是算法？,一个算法通常具有如下特征：输 入：一个算法具有零个或者多个取自指定集合的输入值；输 出：对算法的每一次输入，算法具有一个或多个与输入值相联系的输出值；确定性：算法的每一个指令步骤都是明确的；有限性：对算法的每一次输入，算法都必须在有限步骤（即有限时间）内结束；正确性：对

5、每一次输入，算法应产生出正确的输出值；通用性：算法的执行过程可应用于所有同类求解问题，而不是仅适用于特殊的输入。,10,相关概念：问题和问题实例,问题（Problem）：规定了输入与输出之间的关系，可以用通用语言来描述；问题实例：某一个问题的实例包含了求解该问题所需的输入；排序问题将一系列数按非降顺序进行排序排序问题的一个实例：,11,输入: 由n个数组成的一个序列输出: 对输入系列的一个排列(重排） ，使得,Input: Output: ,相关概念：问题和问题实例,算法可求解的问题：人类基因项目在电子商务中的应用在互联网中的应用（图像检索、视频检索）.重要问题类型：排序、查找、字符串处理、图

6、问题、组合问题、几何问题、数值问题等。,12,相关概念：输入实例与问题规模,输入实例：问题的具体计算例子如，排序问题的3个输入实例：13,5,6,37,8,92,1243,5,23,76,2553,67,32,42,22,33,4,39,56问题规模：算法的输入实例大小。如，上面排序问题的3个输入实例的规模大小分别为7,5,9,13,相关概念：正确算法与不正确算法,正确的算法 如果一个算法对问题每一个输入实例，都能输出正确的结果并停止，则称它为正确的。不正确的算法可能根本不会停止；停止时给出的不是预期的结果；如果算法的错误率可以控制，也是有用的。,14,作为一种技术的算法,15,如果计算机无限

7、快、存储器都是免费的,算法研究是否还需要？Yes！证明方案是正确的，可以给出正确结果。Yes！希望自己的实现符合良好的软件工程实践要求，采用最容易的实现方法。算法对于当代计算机非常重要！类比硬件与软件的不同，算法的迥异带来的意义可能更明显！比如，对100万个数字进行排序：,插入排序: 计算机A: 109 指令/s世界最好的程序员器语言,归并排序: 计算机B: 107 指令/s普通程序员高级语言+低效编译器,问题求解基础,16,算法设计和分析过程,问题求解基础,求解过程说明：理解问题：是否属于已知问题？确定算法输入范围；了解计算设备的性能：清楚速度和计算资源的限制；在精确解法和近似解法之间做选择

8、：有时近似算法是唯一选择；确定适当的数据结构算法的设计技术：这是本课程学习重点和目标；算法的描述：自然语言、流程图、伪代码；算法的正确性证明：证明对于所有合法输入均能产生正确结果；算法的分析：分析执行效率（时间和空间）、简单性、一般性；为算法写代码：利用编程语言以计算机程序行使实现；,17,18,第1章 算法引论,1课程学习背景 1.1 学习动机1.2 算法定义1.3 算法描述2算法复杂性分析2.1 计算模型与算法分析框架2.2 渐进表示,算法描述方法,伪代码拥有自然语言和类编程语言特性，经常被用于算法描述；与真实代码(real code)的差异:对特定算法的描述更加的清晰与精确；不需要考虑太

9、多技术细节（数据抽象、模块、错误处理等）；用伪代码可以体现算法本质；永远不会过时；,19,算法描述方法,20,伪代码的一些约定：书写上的“缩进”(缩排)表示程序中的分程序（程序块）结构；循环结构(while, for, repeat) 和条件结构 (if, then, else) 与Pascal, C语言类似；“/ ” or “ ”来表示注释；利用ije 来表示多重赋值，等价于 je 和ij.变量是局部于给定过程的。数组元素的访问方式: Ai ; A1 . j = 符合数据一般组织成对象，由属性（attribute）或域(field)所组成；域的访问是由域名后跟方括号括住的对象名形式来表示,

10、如lengthA；参数采用按值传递方式；布尔操作 “and” 和“or”具有短路能力: 如 “ x and (or) y ”: 无论y的值如何，必须首先计算x的值。,插入排序的伪代码,问题: 把一系列数据按非递增的顺序排列输入: n 个输入数输出: 输入系列的一个排序 ，使得,INSERTION-SORT(A)1for( j = 2; j 0 & Ai key)5Ai+1 = Ai6i = i-17Ai+1 = key,21,22,第1章 算法引论,1课程学习背景 1.1 学习动机1.2 算法定义1.3 算法描述2算法复杂性分析2.1 计算模型与算法分析框架2.2 渐进表示,算法分析框架,算法

11、分析是指对一个算法所需要的资源进行预测，通常是对计算时间和空间的预测。算法分析的目的是为了从多个候选算法中选择一个最有效的算法，或去掉较差的算法。进行算法分析之前，首先要确立有关实现技术的模型，通常采用随机存取机（RAM）计算模型。默认情况下，算法分析一般是指对算法时间效率的分析。,23,RAM模型,RAM（Random Access machine）：随机访问机算术指令：加法、减法、乘法、除法、取余、取整数据移动指令：装入、存储、复制控制指令：条件与无条件转移、子程序调用与返回单条指令的代价均为常数数据类型（期望运行时间）整数型 vs. 浮点实数型 数据规模为n时，单个数据由c*log n位

12、比特表示其他指令指数运算： 不是常数时间指令， 2 是常数时间指令,24,RAM模型（内存模型）,RAM（Random Access machine）：随机访问机Unit cost assumption模型简单，应用广泛,25,CPU,内存,26,内存层级,现代计算机的存储由多层级组成hierarchy层级离CPU越远，速度越慢，存储容量越大不同层级之间以块（block）的形式移动数据,27,Slow I/O,Disk access is 106 times slower than main memory access,track,magnetic surface,read/write arm

13、,“The difference in speed between modern CPU and disk technologies is analogous to the difference in speed in sharpening a pencil using a sharpener on ones desk or by taking an airplane to the other side of the world and using a sharpener on someone elses desk.” (D. Comer),4835 1915 5748 4125,I/O模型（

14、外存模型）,去掉Unit cost assumption以块（block）形式读取磁盘数据,28,数据流模型,数据流是一个由海量数据组成的数据序列Single Pass: 每个数据最多访问一次Small Space: 存储空间非常小Small time: 更新(插入删除)速度快,CPU,内存：数据摘要,回答近似查询,频繁项有哪些/数据分布是什么/Top-K是什么？,算法分析框架,算法运行时间是指在特定输入时，所执行的基本操作数。输入数据的规模和分布是影响算法运行时间的两个主要因素。 算法时间效率分析框架：算法时间效率用算法输入规模n为参数的函数来度量；对输入规模相同情况下，有些算法的时间效率会

15、有明显差异。对于这样的算法要区分最坏运行时间、最佳运行时间、平均运行时间；对于大规模输入，通常只关注运行时间效率函数的增长率，即只关注函数的高阶项，而忽略低阶项和高阶项系数。,30,算法分析框架,对于规模为n的任何输入，一般考察算法的最坏运行时间：最坏情况运行时间是在任何输入情况下的一个上界；对于某些算法来说，最坏情况出现还是比较频繁的，如信息检索（信息经常不存在）；大致上看，“平均情况”通常和最坏情况一样差。平均运行时间（期望运行时间）概率分析技术( probabilistic analysis ) 随机化算法( randomized algorithm )函数的增长率抽象简化。忽略每条语句

16、的真实代价，用常量c来表示；进一步忽略了抽象的代价；增长率或增长量级。只考虑公式中的最高项，忽略最高项系数和低阶项；,31,插入排序,问题: 把一系列数据按非递增的顺序排列输入: n 个输入数输出: 输入系列的一个排序 ，使得,32,INSERTION-SORT(A)1for( j = 2; j 0 & Ai key)6Ai+1 = Ai7i = i-18Ai+1 = key,33,插入排序,插入排序,总运行时间：,34,如果数组是排好序的，则会出现最好情况：如果数组是逆序排序的，则会出现最差情况： 此时必须将每个元素Aj与整个已排序的子数组A1.j-1中的每一个元素进行比较，对j=2,3,n

17、,有tj=j. 则有：,35,插入排序,DBSCAN的故事,DBSCAN，英文全写为Density-based spatial clustering of applications with noise ，是在 1996 年由Martin Ester, Hans-Peter Kriegel, Jrg Sander 及 Xiaowei Xu 提出的聚类分析算法， 这个算法是以密度为本的：给定某空间里的一个点集合，这算法能把附近的点分成一组（有很多相邻点的点），并标记出位于低密度区域的局外点（最接近它的点也十分远）DBSCAN 是其中一个最常用的聚类分析算法，也是其中一个科学文章中最常引用的。在

18、2014 年，这个算法在领头数据挖掘会议ACM SIGKDD 上获颁发了 Test of Time award，该奖项是颁发给一些于理论及实际层面均获得持续性的关注的算法。,36,DBSCAN的故事,2015年的数据库顶级会议ACM SIGMOD的最佳论文“DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation”中，Junhao Gan和Yufei Tao发现，DBSCAN的算法时间复杂度有误DBSCAN原作者认为算法时间复杂度是O(n log n)的，而实际上是O(n2)该论文在数据挖掘领域和数据库领域都引起论战后来，很多数

19、据挖掘的学者为DBSCAN辩护称，虽然其最坏情况时间复杂度是O(n2)，但是其平均时间复杂度是O(n log n)的理由：假设所有点是均匀分布的前提下，算法的时间复杂度是O(n log n)的其实这仍然不对，为什么？故事的意义：算法的时间复杂度非常关键，受到研究领域的极大重视即使一个经典的算法/论文/定理，仍然有出现错误的可能，需要自己多思考,37,38,第1章 算法引论,1课程学习背景 1.1 学习动机1.2 算法定义1.3 算法描述2算法复杂性分析2.1 计算模型与算法分析框架2.2 渐进表示,39,算法复杂性分析,计算时间的渐近表示记：两个算法的计算时间为函数f(n)与g(n)其中， n

20、 输入或输出规模的某种测度。以下给出算法执行时间：上界（）、下界（）、平均（ ）、低阶(o)的定义。,40,算法复杂性分析,1）上界函数定义1.1 如果存在两个正常数c和n0，对于所有的nn0，有 0 f(n) c*g(n) 则记作f(n) = (g(n)含义：如果算法用 n 值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。则g(n)是计算时间f(n)的一个上界函数。 f(n)的数量级就是g(n)。试图求出最小的g(n)，使得f(n) = (g(n)。,41,Big-oh,42,算法复杂性分析,1）上界函数例1 线性函数 f(n)=3n+2 当n2时， 3n+

21、2 3n+n=4n，故f(n)=O(n) 当n0时， 3n+2 10n，故f(n)=O(n)例2 平方函数 f(n)=10n2 + 4n+2 当n 2时， f(n) 10n2 + 5n ，故f(n)=O(n2) 当n 5时， f(n) 10n2 + n2 = 11n2 ，故f(n)=O(n2),C=4,n0=2,C=10,n0=0,C=10,n0=2,C=10,n0=5,43,算法复杂性分析,1）上界函数例3 指数函数 f(n)=6*2n+n2 当n 4时， n2 2n， f(n) 6*2n+2n= 7*2n ， 故f(n)=O(2n)例4 常数函数 f(n)=9 9*1 故f(n)=O(1)

22、 f(n)=2011 2011*1 故f(n)=O(1),C=7,n0=4,C=9, n0=0,C=2011, n0=0,44,算法复杂性分析,1）上界函数例5 松散界限 f(n)=3n+3 当n 2时， f(n) 3n2，故f(n)=O(n2)例6 错误界限 f(n)=9 *n+2O(1),n2不是最小上限,不存在c0及n0,45,算法复杂性分析,1）上界函数有如下运算规则： (1) (f)+(g)=(max(f,g) (2) (f)+(g)=(f+g) (3) (f)(g)=(fg) (4) 如果g(N)=(f(N)，则(f)+(g)=(f) (5) (Cf(N)=(f(N),其中C是一个

23、正的常数. (6) f=(f),46,算法复杂性分析,多项式定理:定理1 若A(n) = amnm+a1n+a0是一个m次多项 式，则有A(n) = (nm) 即：变量n的固定阶数为m的任一多项式，与此多 项式的最高阶nm同阶。 证明：取n0=1,当nn0时，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|) nm 令c= |am|+|am-1|+|a0| 则，定理得证。,47,算法复杂性分析,大O比率定理: 对于函数f(n)和g(n),若 存在，则f(n)=O ( g(n) )当且仅当存在确定的常数c，

24、有证明：如果f(n)=O ( g(n) )，则存在c0及某个n0, 使得对于所有的nn0，有f(n)/ g(n)c，因此 假定 ，它表明存在一个n0 ， 使得对于所有的nn0，有f(n) max1,c*g(n).,48,算法复杂性分析,例7 因为 所以3n+2= O(n) 因为 所以 10n2 + 4n+2= O(n2) 因为 所以6*2n+n2 = O(2n) 因为 所以3n+3 = O(n2) 因为 所以3n2+3 O(n),49,算法复杂性分析,计算时间的数量级对算法有效性的影响 数量级的大小对算法的有效性有决定性的影响。 例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数

25、量级分别是n2和nlogn。则， n=1024：分别需要1048576和10240次运算。 n=2048：分别需要4194304和22528次运算。 分析：在n加倍的情况下，一个(n2)的算法计算时间增长4 倍，而一个(nlogn)算法则只用两倍多一点的时间即 可完成。,50,算法复杂性分析,算法分类（计算时间）多项式时间算法：可用多项式（函数）对其计算时间限界的算法。 常见的多项式限界函数有： (1) (logn) (n) (nlogn) (n2) (n3)指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数： (2n) (n！) (nn)说明：当n取值较大时，指数时间算法和多

26、项式时间 算法在计算时间上非常悬殊。,51,典型的计算时间函数曲线,52,典型的计算时间函数曲线,当数据集的规模很大时，要在现有的计算机系统上运行具有比(nlogn)复杂度还高的算法是比较困难的。指数时间算法只有在n取值非常小时才实用。要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度，而不是（仅仅依靠）提高计算机的速度。,53,计算时间函数值比较,54,算法复杂性分析,2）下界函数定义1.2 如果存在两个正常数c和n0，对于所有的nn0，有 |f(n)| c|g(n)| 则记作f(n) = (g(n)含义：如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是

27、不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下界函数。试图求出“最大”的g(n)，使得f(n) = (g(n)。,55,Big-omega,56,算法复杂性分析,2）下界函数例1：对于所有的n,有 f(n)=3n+23n, 因此 f(n)= (n) 有f(n)=100n+6100n,因此 f(n)= (n) 3n+2, 100n+6 都是带有下限的线性函数。例2：对于所有的n0,有f(n)=9n2+2n+29n2, 因此f(n)= (n2) 有f(n)=100n2+8n+6100n2, 因此f(n)= (n2),这种下限更有实际意义,57,算法复杂性分析,例2 ：对于所

28、有的n0, 有f(n)=6*2n+n2 6*2n, 因此f(n)= (2n)例3： 3n+2 = (1), 6*2n = (1), 6*2n = (n70), 6*2n = (n5.5),58,算法复杂性分析,比率定理: 对于函数f(n)和g(n),若 存在，则f(n)= ( g(n) )对于确定的常数c，有例4 因为 所以3n+2=(n) 因为 所以10n2+4n+2=(n2) 因为 所以6*2n+n2=(2n) 因为 所以3n2+5(n3),59,算法复杂性分析,3）“平均情况”限界函数定义1.3 如果存在正常数c1，c2和n0，对于所有的nn0，有 c1|g(n)| |f(n)| c2|

29、g(n)| 则记作含义：两个函数就一个常数因子范围内而言是相同的。可看作： 既有f(n) = (g(n)，又有f(n) = (g(n),60,Big-theta,61,算法复杂性分析,3）“平均情况”限界函数例： 3n+2 = (n), 100n+6 = (n) 10n2 +4n+2 =(n2), 1000n2 +10n-6 =(n2) 6*2n +n2 =(2n) 由于3n2+3 O(n)，所以3n2+3 (n) 由于3n2+5(n3)，所以3n2+5 (n3),62,算法复杂性分析,3）“平均情况”限界函数比率定理: 对于函数f(n)和g(n),若 及 存在，则f(n)= ( g(n) )

30、当且仅当存在确定的常数c，有 及例：因为 且 所以3n+2 = (n),63,算法复杂性分析,4） “低阶”与“高阶”限界函数定义1.4 如果对于任意给定的0 ，都存在正整数n0 ，于所有的nn0，有 f(n)/g(n) 则记作 f(n) = o(g(n)含义：当n充分大时，f(n)的阶比g(n)的阶低。例如： 3n+2 = o(n2) 4NlogN+7=o(3N2+4NlogN+7),64,算法复杂性分析,4） “低阶”与“高阶”限界函数定义1.5 如果对于任意给定的0 ，都存在正整数n0 ，于所有的nn0，有 g(n)/f(n) 则记作 f(n) = (g(n)含义：当n充分大时，f(n)

31、的阶比g(n)的阶高。例如： 3n3+2 = (n2) 4N2logN+7=(3N+4NlogN+7),65,算法复杂性分析,5）限界函数的性质1）若 f (g) 且g (h) ，则f (h) 。即具有传递性。（ 、同）2） f (g) 当且仅当 g (f ) 3）若 f (g) ，则 g (f ) 。即定义了一个等价关系（等价类）,66,算法复杂性分析,5. 常用的整数求和公式 在算法分析中，在统计语句的频率时，求和公式的一般表示形式为：其中 f(i) 是一个带有有理数系数且以 i 为变量的多项式。,67,算法复杂性分析,如：,68,69,复杂性分析举例：,70,总结,1算法基本概念 2 复杂性分析方法与手段,71,Thank you!,