算法分析第一章：导论

1、1 主讲教师：孙成敏主讲教师：孙成敏 2015年年3月月 - 2015年年6月月 计算机算法计算机算法 设计与分析设计与分析 2 p类别：专业必修课类别：专业必修课 p学分：学分：3学分学分 p理论学时：理论学时：48 p习题课学时：习题课学时：8 p开课周数：开课周数：1-14周周 3 4 5 计算机算法设计与分析计算机算法设计与分析 王晓东王晓东 电子工业电子工业 计算机算法设计与分析计算机算法设计与分析 苏德富苏德富 电子工业电子工业 6 p这门课程和其他课程的区别是什么这门课程和其他课程的区别是什么? n从这门课程上我能学到哪些东西是在别的课程从这门课程上我能学到哪些东西是在别的课程

2、上学不到的。上学不到的。 p这门课程的研究范畴是什么这门课程的研究范畴是什么? n这门课程的知识可以用来解决什么类型的问题，这门课程的知识可以用来解决什么类型的问题， 应用到什么领域。应用到什么领域。 7 p假设某一负责人交给你一个很难的任务，几天后询问假设某一负责人交给你一个很难的任务，几天后询问 你问题解决了没有。可能会发生如下图这样的情况：你问题解决了没有。可能会发生如下图这样的情况： 问：问：“交给你的问题，解决方法想出来了吗？交给你的问题，解决方法想出来了吗？” 答：答：“我找不到一个有效的方法来解决它，没能完成任我找不到一个有效的方法来解决它，没能完成任 务。务。” 8 问：问：“

3、交给你的问题，解决方法想出来了吗？交给你的问题，解决方法想出来了吗？” 答：答： “ “我找不到一个有效的方法来解决它，因为这样的我找不到一个有效的方法来解决它，因为这样的 方法是不存在的。方法是不存在的。” 要证明一个问题不存在有要证明一个问题不存在有 效的方法，往往比寻找一效的方法，往往比寻找一 种有效方法更难。种有效方法更难。 9 问：问：“交给你的问题，解决方法想出来了吗？交给你的问题，解决方法想出来了吗？” 答：答： “ “我找到了一方法来解决它，理论上可实现的，但是我找到了一方法来解决它，理论上可实现的，但是 以我们目前的力量实现它是不可能的。以我们目前的力量实现它是不可能的。”

4、” 方法消耗方法消耗 的资源太的资源太 大了。大了。 10 p问题能解决吗？问题能解决吗？(可计算性可计算性) p问题解决的好吗？问题解决的好吗？ (计算复杂性计算复杂性) 11 p计算机虽然神通广大，还是计算机虽然神通广大，还是在人的控制下工作在人的控制下工作。 p计算机并非什么都能做，有的事情理论上它计算机并非什么都能做，有的事情理论上它根根 本做不了本做不了。 p讨论哪些事计算机能做，哪些事计算机做不了，讨论哪些事计算机能做，哪些事计算机做不了， 属于属于可计算性可计算性理论研究的范畴。理论研究的范畴。 12 p26个英文字母全排列，它的排列数为个英文字母全排列，它的排列数为 26！41

5、026 p以每年以每年365天计算，共有天计算，共有 3652436003.1536107秒。秒。 p以每秒能完成以每秒能完成107个排列的超高速电子计算机来做个排列的超高速电子计算机来做 这项工作，需要这项工作，需要 41026/(3.1536107107)1.21012 年（千亿年）。年（千亿年）。 13 p有一些问题虽然在理论上能够由计算机解决，但有一些问题虽然在理论上能够由计算机解决，但 因其算法占用资源太多而无法实际完成，因此需因其算法占用资源太多而无法实际完成，因此需 要选择其他算法或改进算法。要选择其他算法或改进算法。 p要知道算法的优劣好坏，就要对算法需要多少计要知道算法的优劣

6、好坏，就要对算法需要多少计 算时间和存储空间做定量的分析。算时间和存储空间做定量的分析。 迄今为止，已有迄今为止，已有20%左右的计算左右的计算 机科学家因其在计算复杂性方面机科学家因其在计算复杂性方面 的研究工作而获得图灵奖。的研究工作而获得图灵奖。 14 p本课程指的计算机是和图灵机计算能力等价的、本课程指的计算机是和图灵机计算能力等价的、 冯诺伊曼体系结构计算机，冯诺伊曼体系结构计算机， 即即确定性图灵机。确定性图灵机。 p量子计算机是非确定性图灵机，其算法和计算复量子计算机是非确定性图灵机，其算法和计算复 杂性完全不同。杂性完全不同。 15 p巡回推销员问题巡回推销员问题 pn皇后问题

7、皇后问题 p背包问题背包问题 16 p 动态规划动态规划 设有设有n个城市，已知任意两城市间之距个城市，已知任意两城市间之距 离，现有一推销员想从某一城市出发巡回经过每离，现有一推销员想从某一城市出发巡回经过每 一城市（且每城市只经过一次），最后又回到出一城市（且每城市只经过一次），最后又回到出 发点，问如何找一条最短路径。试一试求出最短发点，问如何找一条最短路径。试一试求出最短 路径。路径。 17 p 回溯法回溯法 这是高斯这是高斯1850年提出的一个著名问题：年提出的一个著名问题： 国际象棋中的国际象棋中的“皇后皇后”在横向、竖向和斜向都能在横向、竖向和斜向都能 走步和吃子，问在走步和吃子

8、，问在n n 格的棋盘上如何能摆上格的棋盘上如何能摆上n个个 皇后而使她们都不能互相吃。皇后而使她们都不能互相吃。 n当当n很大时，问题很难。很大时，问题很难。 n对于对于n 8，现已知此问题共有，现已知此问题共有92种解，但只有种解，但只有12种是独种是独 立的，其余的都可以由这立的，其余的都可以由这12种利用对称性或旋转而得种利用对称性或旋转而得 到。设到。设n 4，试一试。，试一试。 18 p有一旅行者要从有一旅行者要从3种物品中选取不超过种物品中选取不超过50公斤重的公斤重的 行李随身携带，要求总价值最大。行李随身携带，要求总价值最大。 p物品物品1重重10千克，价值千克，价值60元；

9、物品元；物品2重重20千克，价千克，价 值值100元；物品元；物品3重重30千克，价值千克，价值120元。元。 n动态规划动态规划物品不可分割的前提下，求总价值最大。物品不可分割的前提下，求总价值最大。 n贪心算法贪心算法物品可以分割的前提下，求总价值最大。物品可以分割的前提下，求总价值最大。 19 p D.Knuth The Art of Computer Programming pA.V.Aho , J.Hopcroft , J.Ullman The Design and Analysis of computer Algothms pThomas H.Cormen, Charles E.L

10、eiserson , Ronald L.Rivest Introduction to Algorithms 20 21 2.1 2.1 算算 法法 p什么是算法什么是算法 p算法的重要特性算法的重要特性 p计算过程与算法的区别计算过程与算法的区别 p问题的求解过程问题的求解过程 p算法学习的基本内容算法学习的基本内容 22 p算法是解决一确定类问题的任意一种算法是解决一确定类问题的任意一种特殊特殊的方法。的方法。 n数值计算方法数值计算方法 n非数值计算方法非数值计算方法 p算法的非形式描述：算法就是一组有穷的规则，算法的非形式描述：算法就是一组有穷的规则， 它规定了解决某一特定类型问题的一系

11、列运算。它规定了解决某一特定类型问题的一系列运算。 求解数值问题，插值计算、数值积分等。求解数值问题，插值计算、数值积分等。 求解非数值问题，主要进行判断比较。求解非数值问题，主要进行判断比较。 23 确定性：确定性：每一种运算必须要有确切的定义，无每一种运算必须要有确切的定义，无 二义性；二义性； 能行性：能行性：运算都是基本运算，原则上能在有限运算都是基本运算，原则上能在有限 时间内完成；时间内完成； 输输 入：入：有有0个或多个输入；个或多个输入； 输输 出：出：一个或多个输出；一个或多个输出； 有穷性：有穷性：在执行了有穷步运算后终止；在执行了有穷步运算后终止； 仅仅有穷还不够，还要在

12、现仅仅有穷还不够，还要在现 代计算机上有效才行。代计算机上有效才行。 24 计算过程可以不满足算法的性质计算过程可以不满足算法的性质(5)有穷性。有穷性。 例如操作系统，当没有任务时，操作系统并例如操作系统，当没有任务时，操作系统并 不终止，而是处于等待状态，直到有新的任不终止，而是处于等待状态，直到有新的任 务启动，因而不是一个算法。务启动，因而不是一个算法。 程序程序 算法算法 数据结构数据结构 (By Wirth ) 25 证明正确性证明正确性 分析算法分析算法 理解问题理解问题 精确解或近似解精确解或近似解 算法设计策略算法设计策略 选择数据结构选择数据结构 设计算法设计算法 设计程序

13、设计程序 26 如何设计算法如何设计算法 如何表示算法如何表示算法 如何确认算法如何确认算法 如何分析算法如何分析算法 如何测试程序如何测试程序 27 如何设计算法如何设计算法 p面对具体问题，运用一些基本设计策略，面对具体问题，运用一些基本设计策略， 规划算法。规划算法。 n被实践证明是有用的被实践证明是有用的 n计算机科学、运筹学、电器工程等领域计算机科学、运筹学、电器工程等领域 n设计出很多精致有效的好算法设计出很多精致有效的好算法 p掌握这些策略，设计出更多的好算法。掌握这些策略，设计出更多的好算法。 28 如何表示算法如何表示算法 p设计的算法要用恰当的方式表示出来设计的算法要用恰当

14、的方式表示出来 p采用结构程序设计的方式采用结构程序设计的方式 pSPARKS程序设计语言程序设计语言简单明了简单明了 29 如何确认算法如何确认算法 p算法确认算法确认(algorithm validation)证明该证明该 算法对所有可能的合法输入，都能给出正确答案算法对所有可能的合法输入，都能给出正确答案 p算法确认的目的算法确认的目的确保该算法能正确无误地工作确保该算法能正确无误地工作 n穷举法穷举法 n推理推理数学归纳法、反证法数学归纳法、反证法 n构造性证明构造性证明 n测试测试 30 如何分析算法如何分析算法 p分析执行一个算法时，分析执行一个算法时， n占用占用CPU时间完成运

15、算；时间完成运算； n占用存储器的存储空间，存放程序和数据。占用存储器的存储空间，存放程序和数据。 p即对一个算法需要多少计算时间和存储空间，做即对一个算法需要多少计算时间和存储空间，做 定量分析。定量分析。 31 测试程序测试程序 p 调试调试调试只能指出有错误，而不能指出它们不调试只能指出有错误，而不能指出它们不 存在错误。存在错误。 n源于程序正确性的证明还没有取得突破性进展。源于程序正确性的证明还没有取得突破性进展。 p时空分布图时空分布图 n用各种给定数据执行调试后的程序用各种给定数据执行调试后的程序 n测定计算时间和空间测定计算时间和空间 n印证之前的分析是否正确印证之前的分析是否

16、正确 n指出实现最优化的有效逻辑位置指出实现最优化的有效逻辑位置 32 33 2.2 2.2 分析算法分析算法 p算法分析目的算法分析目的 p算法分析的准备工作算法分析的准备工作 p计算时间的渐进表示计算时间的渐进表示 p一些证明方法一些证明方法 p作时空性能分布图作时空性能分布图 34 算法分析的目的算法分析的目的 p算法分析算法分析(analysis of algorithms)是对一个是对一个 算法需要多少算法需要多少计算时间计算时间和和存储空间存储空间作定量的分析。作定量的分析。 确定算法在什么样的环境下能够有效地运行。确定算法在什么样的环境下能够有效地运行。 p分析在分析在最好最好、

17、最坏最坏和和平均平均情况下的执行情况。情况下的执行情况。 对同一问题不同算法的有效性作出比较。对同一问题不同算法的有效性作出比较。 35 算法运行假定的计算机类型算法运行假定的计算机类型 要求独立于具体的软硬件环境单纯分析算法。要求独立于具体的软硬件环境单纯分析算法。 p假定使用一台通用计算机假定使用一台通用计算机 n顺序处理每条指令；顺序处理每条指令； n存储容量足够大；存储容量足够大； n存取时间恒定。存取时间恒定。 /第第1次课程次课程 36 1. 证明：证明：n2 O(n3) ； 2. 证明：证明：2n2 11n 10 O(n2) ； 3. 证明：证明： O的以下两个性质成立，其中的以

18、下两个性质成立，其中c是一个正是一个正 常数：常数： O(f(n) O(g(n) O(f(n) g(n) ； O(cf(n) O(f(n)； 4. 证明：证明：n3 O(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

19、(n) (max(f(n), g(n)；？；？ 10. (f(n) (g(n) (f(n) g(n)；？；？ 38 算法分析过程算法分析过程 确定算法所涉及确定算法所涉及 的运算的运算 分析算法语句分析算法语句 的执行次数的执行次数 分析算法的执分析算法的执 行时间的渐进行时间的渐进 表示表示 确定出能反映算确定出能反映算 法在各种情况下法在各种情况下 工作的数据集工作的数据集 作时空性作时空性 能分布图能分布图 事前分析事前分析准备工作准备工作事后测试事后测试 全面分析的两个阶段全面分析的两个阶段 39 准备工作准备工作(一一) p首先确定使用哪些首先确定使用哪些运算运算以及执行这些运算以及

20、执行这些运算 所用的时间。所用的时间。 n基本运算基本运算 n由一些更基本的任意长序列的运算所组成的复由一些更基本的任意长序列的运算所组成的复 杂运算杂运算 40 基本运算基本运算 p时间囿界于常数的运算时间囿界于常数的运算 n加、减、乘、除整数算术运算加、减、乘、除整数算术运算 n浮点算术、字符比较、对变量赋值、过程调用等浮点算术、字符比较、对变量赋值、过程调用等 p每种运算所用时间虽然不同，但都只花费一每种运算所用时间虽然不同，但都只花费一 个固定量的时间个固定量的时间 41 复杂运算复杂运算 p由一些更基本的任意长序列的运算组成由一些更基本的任意长序列的运算组成 p如：两个字符串的比较运

21、算如：两个字符串的比较运算 n一系列字符比较指令一系列字符比较指令 n一个字符的比较时间一个字符的比较时间囿界于常数囿界于常数 n字符串比较的时间总量则取决于字符串的长度字符串比较的时间总量则取决于字符串的长度 42 准备工作准备工作(二二) p其次是要确定出能反映算法在各种情况下工作的其次是要确定出能反映算法在各种情况下工作的 数据集。数据集。 n编造出能产生编造出能产生最好最好、最坏最坏和和有代表性有代表性情况的数据配置情况的数据配置 n通过使用这些数据来运行算法，以更了解算法的性能。通过使用这些数据来运行算法，以更了解算法的性能。 算法分析最重要和最算法分析最重要和最 富于创造性的工作。

22、富于创造性的工作。 43 全面分析算法的两个阶段全面分析算法的两个阶段 事前分析事前分析(a prior analysis) 确定每条语句的执行次数。确定每条语句的执行次数。 求出该算法的一个求出该算法的一个时间限界函数时间限界函数(一些关于参数一些关于参数 的函数的函数) 事后测试事后测试(a posterior testing) 收集此算法的实际执行时间和占用空间的统计收集此算法的实际执行时间和占用空间的统计 资料资料 44 算法的执行时间算法的执行时间 p同一条语句在一个算法中的执行次数同一条语句在一个算法中的执行次数 (frequency count )称为频率计数称为频率计数 p语句

23、的时间总量语句的时间总量 频率计数频率计数 执行一次该语句所需要执行一次该语句所需要 的时间的时间 p算法的执行时间就是构成算法的所有语句的执行时算法的执行时间就是构成算法的所有语句的执行时 间总量之和间总量之和 由算法就可直接确定，由算法就可直接确定， 与所用的机器无关，且与所用的机器无关，且 独立于程序设计语言。独立于程序设计语言。 依赖机器、程序设依赖机器、程序设 计语言、编译程序计语言、编译程序 45 例：计算语句例：计算语句xx y在下面三个程序段中的频率计数在下面三个程序段中的频率计数 begin xx y end FC:1 begin for i1 to n do xx y en

24、d FC:n begin for i1 to n do for j1 to n do xx y end FC:n2 语句的数量级是指执行它的频率计数之和语句的数量级是指执行它的频率计数之和 算法的数量级是指算法的所有语句的执行频率之和算法的数量级是指算法的所有语句的执行频率之和 确定一个算法的数量级十分重要，因为它在本质上确定一个算法的数量级十分重要，因为它在本质上 反映了算法所需的计算时间。反映了算法所需的计算时间。 46 p描述算法数量级的多项表达式描述算法数量级的多项表达式 p最高次项最高次项 p最高次项的系数最高次项的系数 p最高次项的次数最高次项的次数 准确分析出算法数量级的多项式表

25、达式是很困难的，准确分析出算法数量级的多项式表达式是很困难的， 因此我们对事前分析的计算时间进行渐进表示。因此我们对事前分析的计算时间进行渐进表示。 47 时间复杂性的形式化定义时间复杂性的形式化定义 p算法的时间复杂性表示为算法的时间复杂性表示为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)是实例是

26、实例I出现的概率。出现的概率。 size(I) n 48 p定义定义2.1：f(n) O(g(n) p定义定义2.2： f(n) (g(n) p定义定义2.3： f(n) (g(n) p定理定理2.1 49 pf(n) 表示算法的计算时间表示算法的计算时间 p n表示问题的规模表示问题的规模 n输入或输出量；输入或输出量； n两者之和；两者之和； n其中之一的某种测度。其中之一的某种测度。 pg(n)是在事前分析中确定的某个形式简单的是在事前分析中确定的某个形式简单的 函数函数 变量和函数的含义变量和函数的含义 与机器和语言有关，而与机器和语言有关，而 是独立于机器和语言的。是独立于机器和语言

27、的。 50 n 当当n充分大时，充分大时， 有上界，一个常数倍的有上界，一个常数倍的)是是 的一个上界，的一个上界， 的数量级就是的数量级就是)。 的阶不高于的阶不高于)的阶。的阶。 n 在确定在确定的数量级时，总是试图求出的数量级时，总是试图求出最小的最小的)。 n 有关证明中，找出有关证明中，找出c和和n0是关键。是关键。 51 例子例子 判断判断 f(n) O(g(n) ？ pf(n) 3n, g(n) 4n pf(n) n 1024, g(n) 1025n pf(n) 2n2 11n 10, g(n) n2 pf(n) n2, g(n) n3 p反例：反例： f(n) n3, g(n)

28、 5n2 52 对于非负的对于非负的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 证明：取证明：取n0 1，当，当n n0时时 由由A(n)的定义和不等式关系的

29、定义和不等式关系|A B| |A| |B| 有有 |A(n)| |amnm a1 n a0 | |am|nm |a1 | n |a0 | (|am| |am 1| n |a0 | nm ) nm (|am| |am 1| |a0 |) nm 取取 c |am| |am 1| |a0 |，有，有|A(n)| cnm 即：即：A(n) O(nm)，定理得证。，定理得证。 54 定理定理2.1表明，变量表明，变量n的最高阶数为的最高阶数为m的任一多项式，的任一多项式， 与与nm同阶。因此一个计算时间为同阶。因此一个计算时间为m阶多项式的算阶多项式的算 法，其时间都可以用法，其时间都可以用O(nm)来

30、表示。来表示。 若一个算法有数量级为若一个算法有数量级为c1nm1，c2nm2， cknmk 的的k个语句，则算法的数量级及计算时间就是个语句，则算法的数量级及计算时间就是 c1nm1 c2nm2 cknmk O(nm) 其中其中 m maxmi|1 i k 55 从计算时间上对算法分类从计算时间上对算法分类 (polynomial time algorithm)： 用多项式来对其计算时间限界的算法用多项式来对其计算时间限界的算法 O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) (exponential time algorithm)： 计算时间用指数函数限界的算

31、法计算时间用指数函数限界的算法 O(2n) O(n ) O(nn) 56 不同时间复杂性函数的对比不同时间复杂性函数的对比 57 58 59 n 当当n充分大时，充分大时，f(n)有下界，一个常数倍的有下界，一个常数倍的g(n)是是 f(n)的一个下界。的一个下界。 n f(n)的阶不低于的阶不低于g(n)的阶。的阶。 n 在确定在确定f(n)的下界时，总是试图求出的下界时，总是试图求出最大的最大的g(n) 。 n 有关证明中，找出有关证明中，找出c和和n0是关键。是关键。 60 对于非负的对于非负的f(n)和和g(n)，根据定义，根据定义2.2，有如下性质：，有如下性质： 1. (f(n)

32、(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(

33、n)意味着该算法在最好和最坏意味着该算法在最好和最坏 情况下的计算时间就一个常数因子范围内而言是相情况下的计算时间就一个常数因子范围内而言是相 同的。同的。 /第第2次课程次课程 62 63 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)

34、 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) 。 类似地

35、，对于任意类似地，对于任意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)

36、 ，存在正常数，存在正常数c1 1和自然数和自然数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 常用的整数求和公式

37、常用的整数求和公式 1n 1(n) i 2 1 (1)/ 2() i n in nn 23 1 (1)(21)/6() i n in nnn 1 1 1 () 12 kk kk i n nn in k 低次项 68 69 70 71 对于正整数对于正整数m, n和实数和实数a 0: a0 1; a1 a ; a-1 1/a ; (am)n amn ; (am)n (an)m ; aman am+n ; a 1 an为为单调递增函数单调递增函数; a 1 nb o(an)lim0 b n n n a 72 23 0 1 2!3! i x i xxx ex i lim1 n x n x e n 7

38、3 log n log2n; lg n log10n; ln n logen; logkn (log n)k; log log n log(log n); for a0, b0, c0 a b ba log 74 log ()loglog ccc abab loglog n bb ana log log log c b c a a b log (1/ )log bb aa 1 log log b a a b loglog bb ca ac 75 |x| 1 for x 1, for any a 0, , logbn O(na) 2345 ln(1). 2345 xxxx xx ln(1) 1

39、x xx x log loglog limlim0 (2 ) bb ana nn nn n 76 10 ! (1)!0 n n n nn ! 1 2 3nn 1 !21 n n nn en 77 !2 n n n nne e 11 12112 n nn !() n no n !(2 ) n n log( !)( log )nnn 78 一些数学证明方法一些数学证明方法 p直接证明：直接证明：PQ p间接证明：间接证明： n反证法反证法 n举反例举反例 p数学归纳法：数学归纳法： n初始归纳：初始归纳：i 1 结论成立；结论成立； n归纳假设：若归纳假设：若i n 1时成立；时成立； n归纳证明

40、：证明归纳证明：证明i n时成立。时成立。 79 p事后测试是在对算法进行设计、确认、事前分析和事后测试是在对算法进行设计、确认、事前分析和 调试之后要做的工作，以确定程序所耗费的精确时调试之后要做的工作，以确定程序所耗费的精确时 间和空间，即作时空性能分布图。间和空间，即作时空性能分布图。与所用计算机密与所用计算机密 切相关切相关。 80 81 SPARKS语言的基本数据类型：语言的基本数据类型： 整型整型(integer), 实型实型(real), 布尔型布尔型(boolean), 字符型字符型(char) SPARKS语言的语言的变量命名规则变量命名规则： 以字母开头，不允许使用特殊字符