算法设计与分析.ppt

《算法设计与分析.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析2013.4,王多强 华中科技大学计算机学院 ,写在讲课前,一、什么是算法 算法就是计算的方法。 数学 数：1，2，3，4， 学：偶数、质数、微积分之数的学问 算法 算：加、减、乘、除 法：何时、何处用何计算之算的方法,写在讲课前（续）,举个例子：排序 问题描述：将一组数按从小到大的顺序整理有序 基本思想：小的数往前排，大的数往后排 怎么排？算法 冒泡排序 选择排序 归并排序 快速排序 堆排序 Shell排序 ,每种算法都是一组特定的规则，规定了一种处理数据的运算方法,问题：既然每种方法都可以实现排序之目的，何必费心研究这么多排序算法？ 其一：就像玩智力游戏，人们乐衷于寻找不同的

2、方法解决各种各样的问题。 其二：研究的需要，算法和算法间是有区别的，我们有必要去研究，去分析。 性质不同：稳定、不稳定 性能不同：速度、空间 适用场合不同 其三，应用的需求，问题有千百万种，没有万能的算法适合所有的应用。需要我们找出算法的设计规律，并设计出解决问题的新算法 怎么选择：根据性能、结合需求、综合选择 如何了解每种算法的性能？算法的分析,二、算法分析 了解算法的性能： 算法速度：快还是慢？如何衡量？怎么比较？ 空间使用量(计算机算法*)：大还是小？如何衡量？怎么比较？ 其它方面的性质等。,实例分析： 排序算法的理论分析：（略） 编程序测试 1.冒泡排序真的很慢吗？ 数据集元素个数：1

3、0、20、1000、10000 2.快速和归并排序都是O(nlogn)的时间复杂度， 到底谁更快一点呢？原因是什么？ 3.冒泡排序会不会比快速排序快？ 来自于实测的结论：可能。,三、为什么要学习算法 1. 编程序的需要 任何程序都需要算法。 the core of computer science 程序 = 数据结构 + 算法 2. 改造世界的需要 世界上还有很多很多的问题等待你解决，有无数的程序等待你去编。 3. 国家综合实力的体现（大） 从软实力的角度，算法是国家科技生产力的核心。是国家综合实力的体现。,四、头疼的事：算法太多了，学不过来 是的，千万的问题、万千的算法。都学过来是不可能的。

4、甚至专一门已经很了不起。 学习算法设计与分析的策略、技术和方法，把握解决问题的规律，为设计更复杂、更有效的算法奠定基础。 需要同学们不断学习，深入思考，创新设计。,五、算法的学习过程：痛苦并快乐着 1.枯燥的过程 繁 /将Ai放到临时变量item中 ji-1 /从后往前查找当前元素的插入位置 while itemA(j) do A(j+1)A(j); /比item大的元素往后移一位 jj-1; /继续往前查找 repeat A(j+1) item; /将item插入到正确的位置上 repeat end INSERTIONSORT,算法导论算法描述： INSERTIONSORT(A,n) A0-

5、 A0做监视哨 for i2 to n 从第二个元素开始循环 do itemAi 将Ai放到临时变量item中 ji-1 从后往前查找当前元素的插入位置 while itemAj do Aj+1Aj 比item大的元素往后移一位 jj-1; 继续往前查找 A(j+1) item; 将item插入到正确的位置上,基于上述算法，思考： 这个算法描述正确吗？ 能行、确定、输入、输出、有穷？ 正确性证明 运算得快吗？ 时间复杂度分析 使用了多少内存？ 空间复杂度分析 进一步我们需要回答： 它能够应用到那些领域？ 要做深入进一步分析 利用不同语言实现需要那些技巧? 实现,4）分析：对算法的时、空特性做定

6、性、定量分析，以了解算法的性质。 5）测试：将算法变成程序，放到计算机上运行，观察运行情况 编程中的调试：排错过程。“调试只能指出有错误， 而不能指出它们不存在错误” Dijkstra的名言 运行中的测试：分析过程。作时空分布图，验证分析结论，进一步优化算法的设计。 本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础,1. 分析算法的目的,算法选择的需要：对同一个问题可以设计不同的算法，不同算法的时间和空间特性是不同的 算法优化的需要：有没有可以改进的地方，以使算法工作得更好？ 分析算法的目的在于：通过对算法的分析了解算法的性

7、能，1）可以在解决同一问题的不同算法之间比较性能的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。2）可以对算法的性质作深入了解，从而可以进一步优化算法，让其更好地工作。,1.2 分析算法基础,2. 重要的假设和约定,1）计算机模型的假设 计算机形式理论模型： 有限状态自动机、Turing机 通用的顺序计算机模型： 单CPU串行算法 有足够的“内存”，并能在固定的时间内存取 数据单元 RAMrandom-access machine 区分计算机的理论模型与实际的计算机,2）计算的约定,算法的执行时间是算法中所有运算执行时间的总和，可以表示为: 算法的执行时间= 其中， fi ：

8、是运算i的执行次数，称为该运算的频率计数 仅与算法的控制流程有关，与实际使用的计算机硬 件和编制程序的语言无关。 ti ：是运算i在实际的计算机上每执行一次所用的时间 与程序设计语言和计算机硬件有关。 如何确定算法使用了哪些运算,每种运算的fi和ti又是多少?,运算的分类,依照运算的时间特性，将运算分为时间囿界于常数的运算和时间非囿界于常数的运算。 囿界的含义：限于. 时间囿界于常数的运算： 基本算术运算，如整数、浮点数的加、减、乘、除 字符运算、赋值运算、过程调用等 特点：执行时间是固定量，与具体的操作数无关。 例： 1+1 = 2 vs 10000+10000 = 20000 100*10

9、0 = 10000 vs 10000*10000 = 100000000 CALL INSERTIONSORT,更一般的情况,设有n种运算c1，c2，cn，它们的执行时间分别是t1，t2，tn。 令t0=max(t1，t2，tn)，则每种运算执行一次的时间都可以用t0进行限界(上界)。 视t0为一个单位时间，则这些运算“理论”上都可视为仅花一个固定的单位时间t0即可完成的运算 称具有这种性质的运算为时间囿界于常数的运算。,运算的分类（续）,时间非囿界于常数的运算： 字符串操作：与字符串中字符的数量成正比 例：字符串的比较运算（strcmp） 记录操作：与记录的属性数、属性类型等有关 特点：运算

10、时间与操作数相关，每次执行的时间是一个不定的量。,怎么分析时间非囿界于常数的运算？ 这类运算通常是由更基本的运算组成的。而这些基本运算是时间囿界于常数的运算。 如：字符串的比较运算是由一组字符比较运算组成的。 非囿界于常数的运算的一次执行时间是其包含的所有基本运算的执行时间之和： 如：字符串比较时间tstring = Length（String）* tchar 故：分析时间非囿界于常数的运算时，只需将其分解成若干时间囿界于常数的运算即可。,3）工作数据集的选择,算法的执行情况与输入数据的特征有关，体现在： 算法的执行时间与输入数据的规模相关，一般 规模越大，执行时间越长。 在不同的数据配置上，

11、同一算法有不同的执行 情况，可分为最好、最坏和平均等情况讨论。 编制不同的数据配置，分析算法的最好、最坏、平均工作情况是算法分析的一项重要工作。 如插入排序有最好O(n)、最坏O(n2)的工作情况。,注：编制测试数据对算法分析与程序调试都是关键的，但目的不同。 算法分析数据集：反映算法的典型执行情况（最好、最坏、平均）； 调试程序数据集：排错。力求走到程序的每个分支，验证各种情况下程序执行正确与否。,3.如何进行算法分析？,对算法的全面分析将分两个阶段进行：事前分析和事后测试（理论分析和程序测试）。 事前分析：求算法时间/空间复杂度的限界函数。 限界函数通常是关于问题规模n的特征函数，被表示成

12、、或的形式。如归并排序的O(nlogn)。 特征函数是通过分析算法的控制逻辑得来的，是对算法所用运算执行次数的统计结果。与使用的程序设计语言和计算机硬件无关。,事后测试：将算法编制成程序，放到实际的计算机上运行，收集程序的执行时间和空间占用情况等统计数据，然后进行分析判断。 事后测试与物理实现直接有关。 算法分析主要集中于与物理实现无关的事前分析阶段获取算法的理论时间/空间复杂度。,1）事前分析,目标：获取算法的时间（空间）复杂度函数，从理论上分析算法性能的好坏。 可以分为时间、空间两个方面： 时间分析： 了解算法中使用了哪些运算(主要是具有单位执行时间的基本运算)。 分析程序的控制流程，从而

13、确定各类运算的执行次数。 将对运算执行次数的统计分析结果表示成关于问题规模n的特征函数。 算法性能有最好、平均、最坏等情况，与数据配置有关。分析典型的数据配置，了解算法在各种情况下的执行情况。,空间分析： 分析算法中各类变量的定义情况和使用情况 将空间占用量表示成为问题规模n的特征函数。 空间占用有最大、平均、最少等情况，与数据配置有关。分析典型的数据配置，了解算法在各种情况下的空间占用情况。,如何进行时间分析？,（一）统计算法中各类运算的执行次数 频率计数 统计对象：运算 1）基本运算：指那些时间囿界于常数的运算 2）复合运算：具有固定执行时间的程序块，如一条语句、一个过程或函数等，它们的一

14、次执行时间也可视为常量、单位时间。 频率计数：运算的执行次数是从算法的控制流程得来的。 顺序结构中的运算：执行次数计为1 嵌套结构中的运算：执行次数等于被循环执行的次数 控制流程分析的关键：确定算法中使用的嵌套结构，包括循环语句、嵌套调用等。,例：执行次数的统计 xx+y for i 1 to n do for i 1 to n do x x + y for j 1 to n do repeat x x +y repeat repeat (a) (b) (c) 分析： (a)： xx+y执行了1次 (b)： xx+y执行了n次 (c)： xx+y执行了n2次,for i 1 to n do f

15、or j i to n do x x +y repeat repeat (d),（二）将频率计数表示成问题规模n的函数： 如： an2+ bn+c 算法的执行时间是算法中各类运算执行时间之和，将正比于各类运算的频率计数之和。 事前分析的频率计数结果与所使用的机器及其他环境因素无关（如程序设计语言、编译器），只与算法本身的控制流程有关。,例：插入分类 procedure INSERTIONSORT(A,n) /将A(1：n)中的元素按非降次序分类，n1/ 执行次数 单位执行时间 A(0)-/设置初始边界值 1 t1 for j2 to n do /A(1:j-1)已分类/ n-1 t2 item

16、A(j); n-1 t3 ij-1 n-1 t4 while itemA(i) do /0ij/ 最多i次,最少1次 t5 A(i+1)A(i); 最多i-1次,最少0次 t6 ii-1; 最多i-1次,最少0次 t4 repeat A(i+1) item; n-1次 t7 repeat end INSERTIONSORT,令 t0=max(t1,t2,t3,t4,t5,t6,t7)，则,最坏情况（逆序）,最好情况（正序）,进一步的分析： 主要针对算法最主要的部分进行分析，抓住主要矛盾即可，如插入排序中,可以仅集中于对for/while双重嵌套循环的分析，而忽略顺序或执行次数较低的部分。 （三

17、）函数表达式的数量级（阶） 函数表达式中的最高次项的次数，称为函数表达式的数量级，是衡量频率计数的“大小”的一种测度。,数量级从本质上反映了算法复杂度的高低 数量级越小，算法的复杂度越低，同等规模下算法执行时间越短。反之， 数量级越大，算法的复杂度越高，同等规模下算法执行时间越长。 例：假如求解同一个问题的三个算法分别具有n， n2 ， n3 数量级。 若n=10，则可能的执行时间将分别是10，100，1000 个单位时间与环境因素无关。 实例：工资的级别 （定性的表示）,（四）限界函数 一般用频率计数函数表达式中的最高次项表示算法复杂性分析的最终结果 限界函数，且忽略掉其系数，记为： g(n

18、)。g(n)通常是关于n的形式简单的函数式，如：logn，nlogn，n2等。 不同算法的g(n)有不同的具体形式。 g(n)通常是对算法中最复杂的计算部分分析而来的。 g(n)忽略了函数表达式中次数较低的“次要”项，体现了算法复杂性的最本质特征。 g(n)通常取单项的形式。 空间特性分析（与时间特性的分析类似，略）,2）事后测试,把算法编制成程序，在实际的计算机硬件平台上运行程序，统计执行中实际耗费的时间与空间，与事前分析的结论进行比较，验证先前的分析结论是否正确，并优化所设计的算法。 分析手段：作时、空性能分布图,4. 计算时间的渐近表示、的定义,算法时间/空间复杂度的限界函数常用的有三个

19、：上界函数、下界函数、“均值”函数。定义如下： 记：算法的实际计算时间为f(n)，计算时间的限界函数为g(n)，其中， n是问题规模的某种测度。 f(n)是与机器及语言有关的量。 g(n)是事前分析的结果，是一个形式简单的函数，与频率计数有关、而与机器及语言无关。,1）O、记号,定义1. 1（上界函数）如果存在两个正常数c和n0，对于所有 的nn0，有|f(n)| c|g(n)|，则记作f(n) = (g(n)。 含义： 如果算法用n值不变的同一类数据（规模相等，性质相同）在某台机器上运行，所用的时间总小于|g(n)|的一个常数倍。 函数f 至多是函数g 的c倍，除非nn0。即是说，当n 充分

20、大时，g 是f 的一个上界函数（在一个非零常数倍的意义下）。 这时候也称f(n)的数量级就是g(n)。,g(n)是通过对算法中运算的使用情况分析而得出的函数表达式，通常情况下，取函数式里的最高次项，舍掉低阶项和常数（因为低阶项和常数最终被湮灭在高次项里），且忽略系数。如： c=O(1)：f(n)等于非零常数，可看作n0 4n+3=O(n) ：可取c5，n03 100n+6=O(n) ：可取 c=101，n06 62n+n2=O(2n) ：可取c =7，n0=4 10n2+4n+3=O(n2) 3log n + 2n + n2 =O(n2) nlog n +n2=O(n2),注： 1总是试图求出

21、数量级最小的g(n)作为f(n)的上界函数，即， g(n)应该尽量接近函数f(n)。数量级越小，限界越精确。 如 若：3n+2=O(n2) 则是松散的界限； 而：3n+2=O(n) 就是较紧的界限。 2不要产生错误界限。 如，n2+100n+6，当nc-100 就有 n2+100n+6cn。 提示：注意大系数低次项的影响 同理，3n2+42n=O(n)也是错误的。,3 f(n)=O(g(n)不能写成g(n)=O(f(n)。 f(n)与g(n)并不等价，这里的等号也并不是通常相等的含义。 O更精确的定义可以用集合表示： O(g(n)=f(n)|f(n)满足：存在正的常数c 和n0，使得当n n0

22、 时，f(n) cg(n) 这里O(g(n)是一个集合，f(n)=O(g(n)读作： “f(n)是g(n)的一个大O 成员” 记作：f(n) O(g(n) 但通常写作：f(n)=O(g(n)。 （以上内容参见Intruduction to AlgorithmChapter 3， 、 相同）,定理1.1 大O比率定理 对于函数f (n)和g (n)，若 存在，则 f (n)=O (g (n) )，当且仅当存在确定的常数c，有 c。 证明： 1）如果f (n)=O (g (n) )，则存在c 0及某个n0，使得对于所有的nn0，有f (n) /g(n)c，因此 c。 2）假定 c，它表明存在一个n

23、0，使得对于所有的nn0，有f (n)max1, c *g (n)。证毕。,例：因为 ，所以5n+2 = O(n) 因为 ，所以7n2+5n+2 = O(n2) 因为 ，所以52n+n2 = O(2n) 考察下式： 因为 ，所以n9+3n2 = O(2n)，是否合适？显然这不是一个好的上界估计。 原因在于：极限值不是一个正常数（见O的定义）。,用于估算复杂性阶的定理,定理1.2 对于任意正实数x 和 ，有下面的不等式： 1) 存在某个n0 , 使得对于任何nn0 , 有(log n)x(log n)x+ 2) 存在某个n0 , 使得对于任何n n0 ，有(log n)x n。 3) 存在某个n

24、0 , 使得对于任何n n0，有nxnx+ 。 4) 存在某个n0 , 使得对于任何nn0 ，有nx2n。 5) 对任意实数y , 存在某个n0，使得对于任何nn0， 有 nx (log n)y nx+,例: 根据定理1.2，很容易得出： n3 + n2 log n = O(n3 ) ； n4 + n2.5 log20 n = O(n4 )； 2n n4 log3 n2n n5 / log3 n = O(2n n5 )。,定义1.2（下界函数） 如果存在两个正常数c和n0，对于所有的nn0，有|f(n)| c|g(n)|，则记作f(n) = (g(n)。 含义： 如果算法用n值不变的同一类数据

25、在某台机器上运行，所用的时间总不小于|g(n)|的一个常数倍。 函数f 至少是函数g 的c 倍，除非n n0 。即是说，当n 充分大时，g 是f 的一个下界函数（在一个非零常数倍的意义下）。,注： 1. 通常情况下，下界函数也取单项的形式。 2. 总是试图求出数量级最大的g(n)作为f(n)的下界函数，g(n)应该尽量接近函数f(n)。 3. 类似于大O 符号，可以参考定理1.2 所列的不等式，来估计复杂性函数的下界。 其它具有和大O类似的性质。,定理1.3 大比率定理 对于函数f (n)和g (n)，若 存在，则 f (n)= (g (n) )，当且仅当存在确定的常数c，有 c。 注： 这里

26、，当n充分大时，g(n) cf (n)意味着 ， 由此不难看出上述判别规则的正确性。,定义1.3（“平均情况”） 如果存在正常数c1，c2和n0，对于所有的nn0，有 c1|g(n)| |f(n)| c2|g(n)|， 则记作 含义： 算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作： 既有 f(n) = (g(n)，又有f(n) = (g(n) 函数f 介于函数g 的c1和c2倍之间，即当n充分大时， g 既是f 的下界，又是f 的上界。,定理1.4 大比率定理 对于函数f (n)和g (n)，若 和 都存在，则 f (n)= (g (n) )，当且仅当存在确定的常数

27、c1和c2，有 c1和 c2。,2）关于算法复杂度的讨论,(1) 数量级的大小对算法的有效性有决定性的影响。 以上界函数O(g(n)为例， 例：假设解决同一个问题的两个算法，它们都有n个输入, 计算时间的数量级分别是n2和nlogn。则， n=1024：分别需要1048576和10240次运算。 n=2048：分别需要4194304和22528次运算。 可以看到： 同等规模n=1024下，计算量有近百倍的差距； 而在规模加倍后，一个(n2)的算法计算时间增长4倍，而一个(nlogn)算法则只增长一倍多一点。,（2）算法时间复杂度的分类,根据上界函数的特性，可以将算法分为：多项式时间算法和指数时

28、间算法。 多项式时间算法：可用多项式函数对计算时间限界的 算法。常见的多项式限界函数有： (1) (logn) (n) (nlogn) (n2) (n3) 指数时间算法：计算时间用指数函数限界的算法。常见的 指数时间限界函数： (2n) (n！) (nn),复杂性越来越高,复杂性越来越高,当n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。 计算时间的典型函数曲线,计算时间函数值比较,表1.1 典型函数的值,对算法复杂性的一般认识,当数据集的规模很大时，要在现有的计算机系统上运行具有比(nlogn)复杂度还高的算法是比较困难的。 指数时间算法只有在n取值非常小时才实用。 要想在顺

29、序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度，而不是（仅仅依靠）提高计算机的速度。,NP问题：Non-deterministic Polynomial，多项式复杂程度的非确定性问题。 什么是非确定性问题呢？ 有些计算问题是确定性的，比如加减乘除之类，只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。 这种问题的答

30、案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。 但对这些问题通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。 完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。,（3）多项式定理,定理1

31、 若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|，即有|A(n)| cnm 。证毕。 应用：如果一个算法的复杂度函数是多项式形式，则其阶函数就可取该多项式的最高次项。,3） 限界函数的性质,传递性：若 且 ， 则 。（ 同） 自反性： 对称性：若 ，则 。 转置对称性： 当

32、且仅当 证明： 从定义出发。 证明过程略。,定理：设d(n)、e(n)、f(n)和g(n)是将非负整数映射到非负实数的函数，则 (1)如果d(n)是O(f(n)，那么对于任何常数a0，ad(n)是O(f(n)； 常数不影响数量级 (2)如果d(n)是O(f(n), e(n)是O(g(n), 那么d(n)+e(n)是O(f(n)+g(n)；加法原理 (3)如果d(n)是O(f(n)， e(n)是O(g(n)，那么d(n)e(n)是O(f(n)g(n)；乘法原理 (4)对于任意固定的x0和a1，nx是O(an)； (5)对于任意固定的x0，lognx是O(logn)；这里x是常数 (6)对于任意固

33、定的常数x0和y0，logxn是O(ny)；,例：2n3+4n2logn=O(n3) 证明：logn=O(n) 规则6 4n2logn=O(4n3) 规则3,乘法原理 2n3+4n2logn=O(2n3+4n3) 规则2, 加法原理 2n3+4n3=O(n3) 规则1、多项式定理 2n3+4n2logn=O(n3),4）o,记号,定义1.4 o记号 形式1：对任意正常数c，存在常数n00，使对所有的nn0，有|f(n)| c|g(n)|，则记作： f(n) = o(g(n)。 形式2：若 则记f(n) = o(g(n)。 例：2n = o(n2)，但2n2 o(n2),O和o的区别,O： o：

34、 在o表示中，当n趋于无穷时，f(n)相对于g(n)来说已经不重要了。,定义1.5 记号 形式1：对任意正常数c，存在常数n00，使对所有的nn0，有c|g(n)|f(n)| ，则记作： f(n) = (g(n)。 形式2：若 则记f(n) = o(g(n)。 例：n2/2 = (n)，但n2/2 (n2),和的区别, ： ： 在表示中，当n趋于无穷时，f(n)相对于g(n)来说变得任意大了。,1.3 分析结论的证明,当我们有了分析的结论，怎么证明结论是正确的？ 常用的方法： 直接推导（略） 数学归纳法 反证法 反例法,1）数学归纳法,数学归纳法是用来证明某些与自然数有关的数学命题的一种推理方

35、法，有广泛的应用。 已知最早的使用数学归纳法的证明出现于 Francesco Maurolico 的 Arithmeticorum libri duo (1575年)。Maurolico 证明了前 n 个奇数的总和是 n2。,数学归纳法采用递推策略进行命题证明，分为标准的二部分完成： 第一步： 基准情形（递归基础、初始情形、平凡情形） 该部分证明定理对于某个（某些）小的值是正确的，一般证明命题在n=1（n0）时命题成立。这是递推的基础。 第二步：归纳假设和推论证明 该部分首先假设定理对于直到某个有限数k（或k以内）的所有情况都成立，然后使用这个假设证明定理对于下一个值（通常就是k+1）也成立。

36、如果证明了k+1正确，则完成整个证明。 完成了上述两步，就可下结论：对任何自然数n（或nn0）结论都正确，证毕。,以上两步密切相关，缺一不可。而且证明的关键是n=k+1时命题成立的推证，这是无限递推下去的理论依据，它将判定命题的正确性由特殊推广到一般，使命题的正确性突破了有限而达到无限。,实例：证斐波那契数Fi(5/3)i 这里：F0 = 1，F1 = 1； Fi = Fi-1 + Fi-2，i2 证明： 1. 初始情形 容易验证F1 = 1 5/3、F2=2(5/3)2， 所以，初始情形成立。 2. 归纳假设 设定理对于i = 1,2,.k都成立，现证明定理对于i=k+1时也成立，即Fk+1

37、(5/3)k+1。,根据定义有， Fk+1 = Fk + Fk-1 将归纳假设用于等号右边，有 Fk+1 (5/3)k + (5/3)k-1 (3/5)(5/3)k+1 + (3/5)2(5/3)k+1 (3/5+9/25)(5/3)k+1 (24/25)(5/3)k+1 (5/3)k+1 n=k+1时结论成立。 由（1）、（2）知，定理得证。,2）反证法,反证法就是通过假设定理不成立，然后证明该假设将导致某个已知的性质不成立，从而证明假设是错误的而原始命题是正确的。 实例：证明存在无穷多个素数 反证法：假设定理不成立。则将存在最大的素数Pk。 令P1,P2,.Pk是依次排列的所有素数，,令

38、：N= P1P2.Pk+1 显然N是比Pk大的数。 思考：N是素数吗？ 因为每个整数，或者是素数，或者是素数的乘积，而N均不能被P1,P2,.Pk整除，因为用P1,P2,.Pk中的任何一个除N总有余数1，所以N是素数。 而NPk，故，与Pk是最大的素数的假设相矛盾。 假设不成立，原定理得证。,3）反例法,反例法就是举一组具体的数据，带入定理给出的表达式，证明该数据计算出来的结果与预想结果不符，从而证明定理的结论有错。 特别的应用：证明定理不成立最直接的方法就是举出一个反例。 例：斐波那契数Fkk2是否成立？ 举反例：令k=11 则：F11 = 144 112，所以原命题不成立。,第一讲小结：

39、1.算法课程的背景介绍 2.算法的定义、性质 3.算法学习涉及的几个方面 4.分析算法的基础 1）计算机模型的假设、计算的约定、数据集的选择 2）分析算法的两个阶段：事前分析、事后测试 3）事前分析：频率计数、数量级、限界函数 5.计算时间的渐进表示： O、 o、记号 6.相关的一些性质 7.证明的方法：数学归纳法、反证法、反例法,作业： 1.试述算法的定义和5个重要性质。 2. 什么是时间囿界于常数的运算？为什么要定义时间囿界于常数的运算？ 3. 什么是算法计算时间的限界函数？ 4. 给出 O、 o、的定义。 5. 用数学归纳法证明： 当n为自然数时，f(n)=32n+2-8n-9能被64整除。,