算法分析第一章：导论.ppt

1,主讲教师：孙成敏 2015年3月 - 2015年6月,计算机算法 设计与分析,2,课程设置,类别：专业必修课 学分：3学分 理论学时：48 习题课学时：8 开课周数：1-14周,3,基本内容,导引 （第一、二章） 基本的算法设计策略 分治法 （第四章） 贪心方法 （第五章） 动态规划 （第六章） 回溯法 （第八章） 分支限界法 （第九章） 基本算法分析方法 NP-难度和NP-完全问题 （第十章）,4,学习目标,掌握基本的算法设计方法 掌握进行算法分析的基本方法（时间、空间复杂度分析） 灵活运用基本的算法设计方法，解决实际问题,5,参考书目,计算机算法设计与分析 王晓东 电子工业 计算机算法设计与分析 苏德富 电子工业,8,问：“交给你的问题，解决方法想出来了吗？” 答： “我找不到一个有效的方法来解决它，因为这样的方法是不存在的。”,要证明一个问题不存在有效的方法，往往比寻找一种有效方法更难。,9,问：“交给你的问题，解决方法想出来了吗？” 答： “我找到了一方法来解决它，理论上可实现的，但是以我们目前的力量实现它是不可能的。”,方法消耗的资源太大了。,问题解决的好吗？,10,现实世界的两个问题,问题能解决吗？(可计算性) 问题解决的好吗？ (计算复杂性),11,可计算性研究的范畴,计算机虽然神通广大，还是在人的控制下工作。 计算机并非什么都能做，有的事情理论上它根本做不了。 讨论哪些事计算机能做，哪些事计算机做不了，属于可计算性理论研究的范畴。,12,一个满足可计算性的问题,26个英文字母全排列，它的排列数为 26！41026 以每年365天计算，共有 3652436003.1536107秒。 以每秒能完成107个排列的超高速电子计算机来做这项工作，需要 41026/(3.1536107107)1.21012年（千亿年）。,13,有一些问题虽然在理论上能够由计算机解决，但因其算法占用资源太多而无法实际完成，因此需要选择其他算法或改进算法。 要知道算法的优劣好坏，就要对算法需要多少计算时间和存储空间做定量的分析。,算法分析研究的范畴,迄今为止，已有20%左右的计算机科学家因其在计算复杂性方面的研究工作而获得图灵奖。,14,本课程的计算机,本课程指的计算机是和图灵机计算能力等价的、冯诺伊曼体系结构计算机， 即确定性图灵机。 量子计算机是非确定性图灵机，其算法和计算复杂性完全不同。,15,几个典型的非数值计算问题,巡回推销员问题 n皇后问题 背包问题,16,巡回推销员问题,动态规划 设有n个城市，已知任意两城市间之距离，现有一推销员想从某一城市出发巡回经过每一城市（且每城市只经过一次），最后又回到出发点，问如何找一条最短路径。试一试求出最短路径。,17,n皇后问题,回溯法 这是高斯1850年提出的一个著名问题： 国际象棋中的“皇后”在横向、竖向和斜向都能走步和吃子，问在nn 格的棋盘上如何能摆上n个皇后而使她们都不能互相吃。 当n很大时，问题很难。 对于n8，现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。设n4，试一试。,背包问题,有一旅行者要从3种物品中选取不超过50公斤重的行李随身携带，要求总价值最大。 物品1重10千克，价值60元；物品2重20千克，价值100元；物品3重30千克，价值120元。 动态规划物品不可分割的前提下，求总价值最大。 贪心算法物品可以分割的前提下，求总价值最大。,19,发展历史,D.Knuth The Art of Computer Programming A.V.Aho , J.Hopcroft , J.Ullman The Design and Analysis of computer Algothms Thomas H.Cormen, Charles E.Leiserson , Ronald L.Rivest Introduction to Algorithms,20,第二章 导 引与基本数据结构,2.1 算法 2.2 分析算法及数学基础 2.3 用SPARKS语言写算法 2.4 基本数据结构（略）,21,2.1 算 法,什么是算法 算法的重要特性 计算过程与算法的区别 问题的求解过程 算法学习的基本内容,22,什么是算法,算法是解决一确定类问题的任意一种特殊的方法。 数值计算方法 非数值计算方法 算法的非形式描述：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。,求解数值问题，插值计算、数值积分等。,求解非数值问题，主要进行判断比较。,23,算法的五个重要特性 确定性：每一种运算必须要有确切的定义，无 二义性； 能行性：运算都是基本运算，原则上能在有限 时间内完成； 输 入：有0个或多个输入； 输 出：一个或多个输出； 有穷性：在执行了有穷步运算后终止；,仅仅有穷还不够，还要在现代计算机上有效才行。,24,计算过程与算法的区别,计算过程可以不满足算法的性质(5)有穷性。 例如操作系统，当没有任务时，操作系统并不终止，而是处于等待状态，直到有新的任务启动，因而不是一个算法。 程序 算法 数据结构 (By Wirth ),25,问题的求解过程,证明正确性,分析算法,理解问题,精确解或近似解 算法设计策略 选择数据结构,设计算法,设计程序,26,算法学习的基本内容 如何设计算法 如何表示算法 如何确认算法 如何分析算法 如何测试程序,27,如何设计算法,面对具体问题，运用一些基本设计策略，规划算法。 被实践证明是有用的 计算机科学、运筹学、电器工程等领域 设计出很多精致有效的好算法 掌握这些策略，设计出更多的好算法。,28,如何表示算法,设计的算法要用恰当的方式表示出来 采用结构程序设计的方式 SPARKS程序设计语言简单明了,29,如何确认算法,算法确认(algorithm validation)证明该算法对所有可能的合法输入，都能给出正确答案 算法确认的目的确保该算法能正确无误地工作 穷举法 推理数学归纳法、反证法 构造性证明 测试,30,如何分析算法,分析执行一个算法时， 占用CPU时间完成运算； 占用存储器的存储空间，存放程序和数据。 即对一个算法需要多少计算时间和存储空间，做定量分析。,31,测试程序,调试调试只能指出有错误，而不能指出它们不存在错误。 源于程序正确性的证明还没有取得突破性进展。 时空分布图 用各种给定数据执行调试后的程序 测定计算时间和空间 印证之前的分析是否正确 指出实现最优化的有效逻辑位置,32,第二章 导 引,2.1 算法 2.2 分析算法及数学基础 2.3 用SPARKS语言写算法 2.4 基本数据结构,33,2.2 分析算法,算法分析目的 算法分析的准备工作 计算时间的渐进表示 一些证明方法 作时空性能分布图,34,算法分析的目的,算法分析(analysis of algorithms)是对一个算法需要多少计算时间和存储空间作定量的分析。 确定算法在什么样的环境下能够有效地运行。 分析在最好、最坏和平均情况下的执行情况。 对同一问题不同算法的有效性作出比较。,35,算法运行假定的计算机类型,要求独立于具体的软硬件环境单纯分析算法。 假定使用一台通用计算机 顺序处理每条指令； 存储容量足够大； 存取时间恒定。 /第1次课程,36,第二章作业 证明：n2O(n3) ； 证明：2n211n 10 O(n2) ； 证明： O的以下两个性质成立，其中c是一个正常数： O(f(n) O(g(n) O(f(n)g(n) ； O(cf(n) O(f(n)； 证明：n3O(n2) ；,37,判断以下命题是否成立，若成立，证明之；不成立，举反例。 5. 如果g(n) (f(n)，则 (f(n) (g(n) (f(n) ；？ 6. (cf(n) (f(n) ，其中c是一个正常数；？ 7. f(n) (f(n) ；？ 8. (f(n) (g(n) (min(f(n), g(n)；？ 9. (f(n) (g(n) (max(f(n), g(n)；？ 10. (f(n) (g(n) (f(n) g(n)；？,38,算法分析过程,确定算法所涉及的运算,分析算法语句的执行次数,分析算法的执行时间的渐进表示,确定出能反映算法在各种情况下工作的数据集,作时空性能分布图,事前分析,准备工作,事后测试,全面分析的两个阶段,39,准备工作(一),首先确定使用哪些运算以及执行这些运算所用的时间。 基本运算 由一些更基本的任意长序列的运算所组成的复杂运算,40,基本运算,时间囿界于常数的运算 加、减、乘、除整数算术运算 浮点算术、字符比较、对变量赋值、过程调用等 每种运算所用时间虽然不同，但都只花费一个固定量的时间,41,复杂运算,由一些更基本的任意长序列的运算组成 如：两个字符串的比较运算 一系列字符比较指令 一个字符的比较时间囿界于常数 字符串比较的时间总量则取决于字符串的长度,42,准备工作(二),其次是要确定出能反映算法在各种情况下工作的数据集。 编造出能产生最好、最坏和有代表性情况的数据配置 通过使用这些数据来运行算法，以更了解算法的性能。,算法分析最重要和最富于创造性的工作。,43,全面分析算法的两个阶段,事前分析(a prior analysis) 确定每条语句的执行次数。 求出该算法的一个时间限界函数(一些关于参数的函数),事后测试(a posterior testing) 收集此算法的实际执行时间和占用空间的统计资料,44,算法的执行时间,同一条语句在一个算法中的执行次数 (frequency count )称为频率计数 语句的时间总量频率计数执行一次该语句所需要的时间 算法的执行时间就是构成算法的所有语句的执行时间总量之和,由算法就可直接确定，与所用的机器无关，且独立于程序设计语言。,依赖机器、程序设计语言、编译程序,45,例：计算语句xxy在下面三个程序段中的频率计数,begin xxy end FC:1,begin for i1 to n do xxy end FC:n,begin for i1 to n do for j1 to n do xxy end FC:n2,语句的数量级是指执行它的频率计数之和 算法的数量级是指算法的所有语句的执行频率之和,确定一个算法的数量级十分重要，因为它在本质上 反映了算法所需的计算时间。,46,计算时间的基本特性,描述算法数量级的多项表达式 最高次项 最高次项的系数 最高次项的次数, ,准确分析出算法数量级的多项式表达式是很困难的， 因此我们对事前分析的计算时间进行渐进表示。,47,时间复杂性的形式化定义,算法的时间复杂性表示为T(n)，其中n是问题的规模。,最坏情况下： Tmax(n)max T(I) | size(I)n 最好情况下： Tmin(n) min T(I) | size(I)n 平均情况下： Tavg(n) P(I) T(I) 其中I是问题规模为n的实例，p(I)是实例I出现的概率。,size(I)n,48,计算时间的渐进表示,定义2.1：f(n) O(g(n) 定义2.2： f(n) (g(n) 定义2.3： f(n) (g(n) 定理2.1,49,f(n) 表示算法的计算时间 n表示问题的规模 输入或输出量； 两者之和； 其中之一的某种测度。 g(n)是在事前分析中确定的某个形式简单的函数,变量和函数的含义,f(n)与机器和语言有关，而 g(n)是独立于机器和语言的。,50,定义2.1,如果存在两个正常数c和n0，对于所有的n n0，有| f(n) | c|g(n)|，则记做f(n)O(g(n) .,当n充分大时， f(n)有上界，一个常数倍的g(n)是 f(n)的一个上界， f(n)的数量级就是g(n)。 f(n)的阶不高于g(n)的阶。 在确定f(n)的数量级时，总是试图求出最小的g(n)。 有关证明中，找出c和n0是关键。,51,例子 判断 f(n) O(g(n) ？,f(n) 3n, g(n) 4n f(n) n1024, g(n) 1025n f(n) 2n2 11n10, g(n) n2 f(n) n2, g(n) n3 反例： f(n) n3, g(n) 5n2,52,O性质,对于非负的f(n)和g(n)，根据定义2.1，有如下性质： 1. O(f(n) O(g(n) O(max(f(n), g(n) ; 2. O(f(n) O(g(n) O(f(n) g(n) ； 3. O(f(n) O(g(n) O(f(n) g(n) ； 4. 如果g(n) O(f(n) ，则O(f(n) O(g(n) O(f(n) ； 5. O(cf(n) O(f(n) ，其中c是一个正的常数； 6. f(n) O(f(n)。,53,定理2.1,若A(n)amnm a1na0是一个m次多项式，则A(n) O(nm),证明：取n01，当nn0时 由A(n)的定义和不等式关系|A B| |A| |B| 有 |A(n)| |amnm a1 n a0 | |am|nm |a1 | n |a0 | (|am| |am1|n |a0 |nm ) nm (|am| |am 1| |a0 |) nm 取 c |am| |am1| |a0 |，有|A(n)| cnm 即：A(n) O(nm)，定理得证。,54,定理2.1表明，变量n的最高阶数为m的任一多项式，与nm同阶。因此一个计算时间为m阶多项式的算法，其时间都可以用O(nm)来表示。,若一个算法有数量级为c1nm1，c2nm2， ， cknmk的k个语句，则算法的数量级及计算时间就是 c1nm1c2nm2 cknmkO(nm) 其中 m maxmi|1 i k,若A(n)amnm a1na0是一个m次多项式，则A(n) O(nm),55,从计算时间上对算法分类,多项式时间算法(polynomial time algorithm)： 用多项式来对其计算时间限界的算法 O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) 指数时间算法(exponential time algorithm)： 计算时间用指数函数限界的算法 O(2n)O(n)O(nn),数量级对算法有效性的影响,56,不同时间复杂性函数的对比,57,小规模数据,58,中等规模数据,59,定义2.2 如果存在两个正常数c和n0，对于所有的nn0，有| f(n) | c |g(n)|，则记做f(n) (g(n) .,当n充分大时，f(n)有下界，一个常数倍的g(n)是f(n)的一个下界。 f(n)的阶不低于g(n)的阶。 在确定f(n)的下界时，总是试图求出最大的g(n) 。 有关证明中，找出c和n0是关键。,60,性质,对于非负的f(n)和g(n)，根据定义2.2，有如下性质： 1. (f(n) (g(n) (min(f(n), g(n) ; 2. (f(n) (g(n) (f(n) g(n) ； 3. (f(n) (g(n) (f(n) g(n) ； 4.如果g(n) (f(n) ，则(f(n) (g(n) (f(n) ； 5. (cf(n) (f(n) ，其中c是一个正的常数； 6.f(n) (f(n)。,61,定义2.3 如果存在两个正常数c1, c2和n0，对于所有的n n0，有 c1 |g(n)| |f(n)| c2 |g(n)|，则记作：f(n)(g(n) .,一个算法的f(n)(g(n)意味着该算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。 /第2次课程,62,渐近表示函数的若干性质,（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)； （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).,63,（5）算术运算 O(f(n) O(g(n) O(maxf(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) ； f(n) O(g(n) O(f(n) O(g(n) O(g(n) 。 、 也有类似性质，证明方法类似。,渐近表示函数的若干性质,64,规则O(f(n)O(g(n) O(maxf(n), g(n) 的证明： 对于任意f1(n) O(f(n) ，存在正常数c1和自然数n1，使得对所有 n n1，有f1(n) c1f(n) 。 类似地，对于任意g1(n) O(g(n) ，存在正常数c2和自然数n2， 使得对所有n n2，有g1(n) c2g(n) 。 令c3 maxc1, c2， n3 maxn1, n2，h(n) maxf(n),g(n) 。 则对所有的 n n3，有 f1(n) g1(n) c1f(n) c2g(n) c3f(n) c3g(n) c3(f(n) g(n) 2c3 maxf(n), g(n) 2c3h(n) O(maxf(n),g(n) .,65,规则O(f(n)O(g(n) O(f(n)g(n) 的证明： 对于任意f1(n) O(f(n) ，存在正常数c1和自然数n1，使得对所有 n n1，有f1(n) c1f(n) 。 类似地，对于任意g1(n) O(g(n) ，存在正常数c2和自然数n2， 使得对所有n n2，有g1(n) c2g(n) 。 令c3 maxc1, c2， n3 maxn1, n2，h(n) f(n)g(n) 。 则对所有的 n n3，有 O(f(n) O(g(n) f1(n) g1(n) c1f(n) c2g(n) c3f(n) c3g(n) c3(f(n) g(n) c3h(n) O(f(n) g(n) .,66,规则O(f(n)O(g(n) O(f(n) g(n) 的证明： 对于任意f1(n) O(f(n) ，存在正常数c11和自然数n1， 使得对所有 n n1，有f1(n) c1f(n) 。 类似地，对于任意g1(n) O(g(n) ，存在正常数c2 1和自然数n2， 使得对所有n n2，有g1(n) c2g(n) 。 令c3 c1 c2， n3 maxn1, n2，h(n) f(n) g(n) 。 则对所有的 n n3，有 O(f(n) O(g(n) f1(n) g1(n) c1f(n) c2g(n) c3f(n) g(n) c3h(n) O(f(n) g(n) .,67,数学基础,（1）常用的整数求和公式 通式,68,算法渐近复杂性分析中常用函数,（2）单调函数 单调递增：m n f(m) f(n) ; 单调递减：m n f(m) f(n); 严格单调递增：m n f(m) f(n); 严格单调递减：m n f(m) f(n). （3）取整函数 x ：不大于x的最大整数； 2.5 2 2 2 x ：不小于x的最小整数。 2.5 3 2 2,69,取整函数的若干性质,x1 x x x x 1； n/2 n/2 n; 对于n 0，a, b0，有： na b nab ; na b nab ; ab (a(b 1)b; ab (a (b 1)b; f(x) x , g(x) x 为单调递增函数。,70,（4）多项式函数 p(n) a0 a1n a2n2 adnd； ad0; p(n) (nd); p(n) O(nk) p(n)多项式有界； p(n) O(1) p(n) c;,71,指数函数一些性质 对于正整数m, n和实数a 0: a01; a1 a ; a-1 1/a ; (am)n amn ; (am)n (an)m ; aman am+n ; a 1 an为单调递增函数; a 1 nb o(an),72,ex 1+x; |x| 1 1x ex 1 x x2 ; ex 1 x (x2), as x0;,73,log n log2n; lg n log10n; ln n logen; logkn (log n)k; log log n log(log n); for a0, b0, c0,（5）对数函数,74,75,|x| 1 for x 1, for any a 0, , logbn O(na),76,（6）阶乘函数 Stirlings approximation,77,78,一些数学证明方法,直接证明：PQ 间接证明： 反证法 举反例 数学归纳法： 初始归纳：i1 结论成立； 归纳假设：若in1时成立； 归纳证明：证明in时成立。,79,时空分布图,事后测试是在对算法进行设计、确认、事前分析和调试之后要做的工作，以确定程序所耗费的精确时间和空间，即作时空性能分布图。与所用计算机密切相关。 以时间分布图为例，要求： 时钟及其精确度 操作系统的工作方式 解决因时钟误差引起的噪声问题，推荐两种方法： 增加输入规模 增加执行次数 时空分布图的做法 用途 比较同一问题的不同算法 对算法改进前后进行比较,80,主要内容,2.1 算法 2.2 分析算法及数学基础 2.3 用SPARKS语言写算法 2.4 基本数据结构,81,2.3 用SPARKS语言写算法,SPARKS语言的基本数据类型： 整型(integer), 实型(real), 布尔型(boolean), 字符型(char),SPARKS语言的变量命名规则： 以字母开头，不允许使用特殊字符，不允许与保留字重复,赋值语句：变量 表达式,逻辑运算符：and , or , not 关系运算符： ， ,布尔值: true，false,数组：任意整数下界和上界的多维数组 integer A(l1:u1, , ln:un);,例: integer x, y; char ch;,例: integer A(1:10); real B(3:6 , 1:4);,82,SPARKS语言的条件语句,if 条件 then s1 endif if 条件 then s1 else s2 endif,case : 条件 1: s1 : 条件 n: sn : else : sn1 endcase,SPARKS语言的case语句,2.3 用SPARKS语言写算法,83,SPARKS语言的循环语句,while 条件 do S rep