算法分析与设计课件：第一章 绪言下

《算法分析与设计课件：第一章 绪言下》由会员分享，可在线阅读，更多相关《算法分析与设计课件：第一章 绪言下（124页珍藏版）》请在装配图网上搜索。

1、算法设计的步骤2022-7-192 of 158一、问题的陈述一、问题的陈述已知什么，求什么，提附加问题以帮已知什么，求什么，提附加问题以帮助理解用户的要求助理解用户的要求二、模型的拟制二、模型的拟制1）为什么要建立模型）为什么要建立模型计算机解决大而复杂的问题，需要数计算机解决大而复杂的问题，需要数学模型学模型2）建模的两条途径）建模的两条途径2022-7-193 of 158 A 寻找最适合这个问题的数学结构寻找最适合这个问题的数学结构B 借鉴已经解决了的类似问题借鉴已经解决了的类似问题3)如何选数学工具表示已知的和要求的量如何选数学工具表示已知的和要求的量A 设计人员掌握的数学知识设计人

2、员掌握的数学知识B 数学结构是否表达方便数学结构是否表达方便C 计算是否简单计算是否简单4)对不同模型要进行比较，选出最有效的对不同模型要进行比较，选出最有效的模型模型2022-7-194 of 158n例：货郎担例：货郎担(TSP)问题问题设售货员要到五个城市去售货，最后设售货员要到五个城市去售货，最后再回到出发的城市。已知从一个城市再回到出发的城市。已知从一个城市到其他城市的费用，求总费用最少的到其他城市的费用，求总费用最少的路线路线2022-7-195 of 158n解：下面给出称为登山法的算法。解：下面给出称为登山法的算法。所谓登山法，就是从初始结点出发，满足所谓登山法，就是从初始结点

3、出发，满足某些约束条件，一步一步地某些约束条件，一步一步地“登到登到”终点。终点。设设n阶无向带权完全图阶无向带权完全图G=1）以）以vi为起点，在其余的为起点，在其余的n-1个结点中，找个结点中，找出最邻近于出最邻近于vi的结点的结点vj（vj可能不唯一，可能不唯一，但只选一个），形成初级通路但只选一个），形成初级通路vi vj 2）在其余的）在其余的n-2个城市中找出最邻近于个城市中找出最邻近于vj的的结点结点vk，形成初级通路，形成初级通路 vi vj vk2022-7-196 of 158 如此进行下去，直到将所有结点都扩如此进行下去，直到将所有结点都扩充到通路中来，最后得到长度为充到

4、通路中来，最后得到长度为n的的初级通路就是图中一条哈密顿回路，初级通路就是图中一条哈密顿回路，将它的权做为图中最短哈密顿回路长将它的权做为图中最短哈密顿回路长度的近似值。这个算法就是登山法。度的近似值。这个算法就是登山法。此算法的结果与所选择的起点有关。此算法的结果与所选择的起点有关。2022-7-197 of 158权为13从不同结点出发：从不同结点出发：1）结点）结点a为起点：为起点：2）结点）结点b为起点：为起点：3）结点）结点c为起点：为起点：4）结点）结点d为起点：为起点：权为13权为13权为13abcd213743或者152022-7-198 of 158n而实际上图中最短哈密顿而

5、实际上图中最短哈密顿回路的长度为回路的长度为12。即即abcdaabcd2137432022-7-199 of 158三、算法的详细设计三、算法的详细设计1）算法的选择与模型有关。）算法的选择与模型有关。2）算法详细设计的含义）算法详细设计的含义是指设计求解某个具体问题类的一系是指设计求解某个具体问题类的一系列步骤，并且这些步骤可以通过计算列步骤，并且这些步骤可以通过计算机的各种操作来实现机的各种操作来实现四、算法的正确性四、算法的正确性2022-7-1910 of 158五、算法的实现五、算法的实现 1）完善子程序）完善子程序 2）选合适的数据结构）选合适的数据结构六、算法的分析六、算法的分

6、析 分析的理由：分析的理由：1）估计该算法的存储空间和）估计该算法的存储空间和运行空间运行空间 2）建立衡量算法优劣的标准）建立衡量算法优劣的标准七、程序的测试七、程序的测试1）测试是证实程序是否完成既定任务的）测试是证实程序是否完成既定任务的手段，并可确定程序的适用范围手段，并可确定程序的适用范围2022-7-1911 of 1582）测试的方法）测试的方法a)白盒测试白盒测试 对程序的每个分支进行测试对程序的每个分支进行测试b)黑盒测试黑盒测试 检查对给定的输入是否有指定的输出检查对给定的输入是否有指定的输出八、文档编制八、文档编制目的：使别人了解自己的算法和程序目的：使别人了解自己的算法

7、和程序算法的复杂性2022-7-1913 of 158符号2022-7-1914 of 158符号2022-7-1915 of 158符号n2 对数对数logn=log2n lgn=log10n lg2=0.3012022-7-1916 of 158符号n证明：证明：nbalognbbablogloganbbblogloganbbbloglog)(abnlog2022-7-1917 of 158符号nlogbN=logaN/logabnlogeN=lnN ne=2.71828nlogab=1/logba2022-7-1918 of 158符号2022-7-1919 of 158符号n三、求和三

8、、求和等比级数和调和级数的求和公式等比级数和调和级数的求和公式 nknnkkOnkxxx110)1(ln1112022-7-1920 of 158符号2022-7-1921 of 1581、衡量算法优劣的标准：时空复杂性、衡量算法优劣的标准：时空复杂性2、问题规模：与问题相关的整数量，、问题规模：与问题相关的整数量，它可以衡量问题的规模并表示输入数它可以衡量问题的规模并表示输入数据量的尺度。也称为问题尺度据量的尺度。也称为问题尺度3、算法的时间复杂性：处理一个尺度、算法的时间复杂性：处理一个尺度为为n的输入，算法所需要的的输入，算法所需要的时间时间，记，记为为T(n)2022-7-1922 o

9、f 1583、算法的时间复杂性：处理一个尺度、算法的时间复杂性：处理一个尺度为为n的输入，算法所需要的输入，算法所需要的执行次数的执行次数（或执行的步数）（或执行的步数），记为，记为T(n)2022-7-1923 of 1584、渐进时间复杂性：、渐进时间复杂性：当问题的尺度增加时，时间复杂性的当问题的尺度增加时，时间复杂性的极限极限5、算法的空间复杂性：、算法的空间复杂性：处理一个尺度为处理一个尺度为n的输入，算法所需要的输入，算法所需要的空间数，记为的空间数，记为S(n)2022-7-1924 of 1586、渐进空间复杂性：、渐进空间复杂性：当问题的尺度增加时，空间复杂性的当问题的尺度增

10、加时，空间复杂性的极限极限7、时空综合复杂性、时空综合复杂性 T(n)S(n)2022-7-1925 of 1588、算法复杂性的阶、算法复杂性的阶处理尺度为处理尺度为n的输入，需要执行的输入，需要执行Cn2次次,则算法复杂性是则算法复杂性是O(n2)，读作，读作“n2阶阶”2022-7-1926 of 158第一种理解方法2022-7-1927 of 158第二种理解方法n求复杂性函数阶的极限方法求复杂性函数阶的极限方法例如，f(n)=n2/4,g(n)=n2,则n2/4=(n2)f(n)=logn,g(n)=n,则logn=O(n);()()();()()(0);()()(0)()(lim

11、gfngnfsgOfngnfsgfngnfssngnfn则的阶高，比说明时，当则的阶低，比说明时，当则同阶，和说明时，当若2022-7-1928 of 158f(n)c0g(n)c1g(n)n0f(n)is(g(n)f(n)cg(n)n0f(n)is O(g(n)f(n)cg(n)n0f(n)is(g(n)2022-7-1929 of 158例例1 0.25n2=O(n2)（相差常数因子）（相差常数因子）0.73n2O(n)（阶不等）（阶不等）n(n+1)/3=O(n2)（相差低阶项）（相差低阶项）5n4 6n2+1=O(n4)(相差低阶项和常相差低阶项和常数因子数因子)2022-7-1930

12、 of 158等式等式 0.75n2=O(n)何时成立？何时成立？永不成立永不成立等式等式3n1/2=O(n)在在n=9时成立吗？时成立吗？n=9时，虽然两边值相等，但等式不成时，虽然两边值相等，但等式不成立立2022-7-1931 of 158n例例2：60n2+5n+1 n60n2+5n+1 60n2+5n2+n2=66n2 对于对于n 1n所以所以 60n2+5n+1=O(n2)n又又60n2+5n+1 60n2 对于对于n 1n所以所以 60n2+5n+1=(n2)n综上综上 60n2+5n+1=(n2)2022-7-1932 of 1582022-7-1933 of 158n例例4：

13、1+2+n n1+2+n n+n+n=n2 对于对于n 1n所以所以 1+2+n=O(n2)n又又1+2+n 1+1+1=n 对于对于n 1n所以所以 1+2+n=(n)n综上综上 1+2+n=?2022-7-1934 of 158n又又1+2+n nnn)1(.222.22nnnn 221nn4222nnn2022-7-1935 of 158n所以所以 1+2+n=(n2)n综上综上 1+2+n=(n2)n练习：练习：n1、给出、给出1k+2k+nk 的的 表示表示n2、给出、给出logn!的的 表示表示n1、1k+2k+nk=(nk+1)n2、logn!=(nlogn)2022-7-193

14、6 of 158n求上界的方法求上界的方法2022-7-1937 of 1582022-7-1938 of 1582022-7-1939 of 1582022-7-1940 of 158n求下界的方法：求下界的方法：n缩小法缩小法2022-7-1941 of 158n标准复杂性函数的比较标准复杂性函数的比较O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn)注意：注意：1）不能划等号）不能划等号 2）以下若无特殊声明，）以下若无特殊声明，log是以是以2为底的对数为底的对数 3）上式只有在）上式只有在n较大的时候成立较大的时候成立O(1)的含义？的含

15、义？计算时间由一个常数（零次多项式）来限界计算时间由一个常数（零次多项式）来限界多项式时间阶多项式时间阶指数时间阶指数时间阶2022-7-1942 of 158指数时间指数时间一个算法的时间复杂性如果是一个算法的时间复杂性如果是O(2n)，则称，则称此算法需要指数时间。此算法需要指数时间。多项式时间多项式时间一个算法的时间复杂性如果是一个算法的时间复杂性如果是O(nk)(k为有为有理数），则称此算法需要多项式时间。理数），则称此算法需要多项式时间。有效算法有效算法以多项式时间为限界的算法称为有效算法。以多项式时间为限界的算法称为有效算法。2022-7-1943 of 158Time to Fi

16、nishInput Size(n)O(nx)O(n)O(1)O(n lg n)O(an)2022-7-1944 of 1582022-7-1945 of 1582022-7-1946 of 158例n例：算法例：算法A1,A2的时间复杂性分别是的时间复杂性分别是n,2n,设设100s是一个单位时间，求是一个单位时间，求A1,A2在在1s内能处理的问题规模。内能处理的问题规模。n已知已知lg2=0.3012022-7-1947 of 158复杂性的基本概念n有效算法：有效算法：以多项式时间为限界的算法。以多项式时间为限界的算法。n按算法的时间复杂性，可以把问题分为按算法的时间复杂性，可以把问题分

17、为3类：类：1）p类问题类问题能以多项式时间为界的算法解决的问题能以多项式时间为界的算法解决的问题2022-7-1948 of 1582）NP类问题：已知的最好算法是以非类问题：已知的最好算法是以非多项式时间为界的问题。多项式时间为界的问题。3）写不出算法的问题。）写不出算法的问题。实际上可计算的问题：实际上可计算的问题：多项式时间可解的问题多项式时间可解的问题2022-7-1949 of 158有时，算法中基本操作重复执行的次数会有时，算法中基本操作重复执行的次数会随问题的输入数据集不同而不同。随问题的输入数据集不同而不同。比如：冒泡法排序比如：冒泡法排序n个整数个整数1）当原始数据是从小到

18、大有序排列时，则）当原始数据是从小到大有序排列时，则基本操作（交换序列中相邻的两个整数）基本操作（交换序列中相邻的两个整数）的执行次数为的执行次数为02022-7-1950 of 1582）当原始数据是从大到小有序排列时，）当原始数据是从大到小有序排列时，基本操作的执行次数为基本操作的执行次数为n(n-1)/2n解决方法：解决方法：1）求平均情况的时间复杂性）求平均情况的时间复杂性 即考虑算法对所有可能的输入数据集的期即考虑算法对所有可能的输入数据集的期望值，此时对应的时间复杂性为算法的平望值，此时对应的时间复杂性为算法的平均时间复杂性。均时间复杂性。2022-7-1951 of 158n2）

19、求最坏情况的时间复杂性）求最坏情况的时间复杂性 即分析最坏情况以估算算法执行时间即分析最坏情况以估算算法执行时间的一个上界。的一个上界。2022-7-1952 of 158两点说明：两点说明：1）用基本操作重复执行的次数作为算）用基本操作重复执行的次数作为算法的时间复杂性比较粗略法的时间复杂性比较粗略2）在实践中我们可以把算法的事前分）在实践中我们可以把算法的事前分析和事后统计两种方法结合起来使用。析和事后统计两种方法结合起来使用。2022-7-1953 of 158例：若上机运行了一个问题尺度为例：若上机运行了一个问题尺度为10的算法，执行时间为的算法，执行时间为6ms，并且算法，并且算法的

20、时间复杂性为的时间复杂性为T(n)=O(n2)，则可以，则可以估算问题尺度为估算问题尺度为21时，所需时间大致时，所需时间大致为为 （21/10)26ms26.5ms随机存取机随机存取机(RAM)2022-7-1955 of 158nRAM的结构示意图的结构示意图 x1x2只读输入带程序存储器指令计数器y1y2只写输出带累加器内存储器r0r1r22022-7-1956 of 1581.RAM的组成的组成1）只读输入带：被划分成一系列方格，每）只读输入带：被划分成一系列方格，每个方格可存放任意大小的整数。每当从输个方格可存放任意大小的整数。每当从输入带中读出一个数据时，带头就自动向右入带中读出一

21、个数据时，带头就自动向右移动一格。初始时，其上依次存放有算法移动一格。初始时，其上依次存放有算法运行所需的全部初始数据。运行所需的全部初始数据。2022-7-1957 of 1582）只写输出带：被划分成一系列方格，）只写输出带：被划分成一系列方格，每个方格可存放任意大小的整数。每每个方格可存放任意大小的整数。每输出一个数据，带头就自动向右移动输出一个数据，带头就自动向右移动一格。初始时，其上所有方格为空。一格。初始时，其上所有方格为空。3）程序存储器：只存放程序）程序存储器：只存放程序4）指令计数器：控制程序走向，即确）指令计数器：控制程序走向，即确定下一条要执行的指令。定下一条要执行的指令

22、。2022-7-1958 of 1585）内存储器：由一系列寄存器）内存储器：由一系列寄存器r0,r1,r2,组组成，每个寄存器都能存放一个任意大小的成，每个寄存器都能存放一个任意大小的整数。寄存器的个数是任意的。其中，第整数。寄存器的个数是任意的。其中，第一个寄存器一个寄存器r0称为累加器，所有的运算都称为累加器，所有的运算都在其中进行。在其中进行。2022-7-1959 of 1582.RAM的指令系统的指令系统一条一条RAM指令一般由操作码和操作数指令一般由操作码和操作数组成。组成。例如：例如：指令指令 STORE i 表示把累加表示把累加器中的内容送入内存器中的内容送入内存ri中中 其

23、中其中STORE 是操作码：操作定义符，是操作码：操作定义符，指明操作意义指明操作意义 i是操作数：指示操作对象是操作数：指示操作对象2022-7-1960 of 158操作数的获得有三种方式：操作数的获得有三种方式：1）立即寻址方式：）立即寻址方式：=i，操作数是整数，操作数是整数i本身本身2）直接寻址方式：）直接寻址方式：i，i是非负整数，操作是非负整数，操作数是寄存器数是寄存器i中的内容，用中的内容，用c(i)表示表示3）间接寻址方式：）间接寻址方式：*i，操作数是以寄存器，操作数是以寄存器 ri的内容为地址的寄存器中的内容，的内容为地址的寄存器中的内容，用用c(c(i)表示。当表示。当

24、c(i)0 0 否则否则n内存内存r1,r2,r3 分别存储变量分别存储变量n,t2,t3,其中其中t2作为中间结果或输出结果，作为中间结果或输出结果，t3作为作为计数器。计数器。2022-7-1973 of 158程序int f(int n)if(n0)t2=t2*n;t3=t3-1;return t2;内存内存r1,r2,r3 分别存储变分别存储变量量n,t2,t3,其其中中t2作为中间作为中间结果或输出结果或输出结果，结果，t3作作为计数器。为计数器。2022-7-1974 of 158READ 1LOAD 1JGTZ posWRITE =0JUMP endifnif(n0)while:

25、LOAD 3JGTZ continueJUMP endwhilet2=t2*n;continue:LOAD 2MULT 1STORE 2 内存内存r1,r2,r3 分别存储变分别存储变量量n,t2,t3,其其中中t2作为中作为中间结果或输间结果或输出结果，出结果，t3作为计数器。作为计数器。2022-7-1976 of 158t3=t3-1;LOAD 3SUB =1STORE 3JUMP whilereturn t2;endwhile:WRITE 2endif:HALT内存内存r1,r2,r3 分别存储变分别存储变量量n,t2,t3,其其中中t2作为中间作为中间结果或输出结果或输出结果，结果，

26、t3作作为计数器。为计数器。2022-7-1977 of 1585.RAM程序的复杂性程序的复杂性n最坏情况时间复杂性：对于输入尺度最坏情况时间复杂性：对于输入尺度为为n的各种输入执行每条命令所需时的各种输入执行每条命令所需时间之和的最大值。间之和的最大值。n平均情况时间复杂性：对于输入尺度平均情况时间复杂性：对于输入尺度为为n的各种输入执行每条命令所需时的各种输入执行每条命令所需时间之和的平均值。间之和的平均值。2022-7-1978 of 158两种时空耗费标准：两种时空耗费标准：n1）均匀耗费标准：规定每执行一条）均匀耗费标准：规定每执行一条RAM指令需要一个单位时间，每个指令需要一个单

27、位时间，每个寄存器需要占用一个单位空间。寄存器需要占用一个单位空间。优点：方便快捷优点：方便快捷缺点：比较粗略缺点：比较粗略n均匀耗费标准均匀耗费标准 平均情况复杂性平均情况复杂性2022-7-1979 of 1582）对数耗费标准：）对数耗费标准：n一个一个RAM程序的时空耗费与数据的程序的时空耗费与数据的长度有直接关系：长度有直接关系：n设设l(i)是整数是整数i所占的二进制数位，则所占的二进制数位，则0101|log)(iiiil2022-7-1980 of 158(一一)对数时间复杂性对数时间复杂性 假设执行一条指令的耗费与参与这条假设执行一条指令的耗费与参与这条指令的数据的长度之和成

28、比例。指令的数据的长度之和成比例。耗费耗费数据的长度之和数据的长度之和例例1 MULT=i 的耗费的耗费 l(i)+l(c(0)2022-7-1981 of 158例例2 MULT i 的耗费的耗费 l(i)+l(c(i)+l(c(0)例例3 MULT *i 的耗费的耗费 l(i)+l(c(i)+l(c(c(i)+l(c(0)例例4 JUMP b 的耗费的耗费 常数常数12022-7-1982 of 158例例5 JGTZ b 的耗费的耗费 l(c(0)例例6 HALT 的耗费的耗费 常数常数1操作数操作数a对数时间耗费对数时间耗费t(a)=il(i)il(i)+l(c(i)*il(i)+l(

29、c(i)+l(c(c(i)2022-7-1983 of 158指令指令对数时间耗费对数时间耗费LOAD at(a)STORE il(c(0)+l(i)SUB al(c(0)+t(a)MULT al(c(0)+t(a)READ il(i)+l(input)WRITE at(a)JUMP b1JGTZ bl(c(0)HALT12022-7-1984 of 158(二二)对数空间复杂性对数空间复杂性 所有寄存器（包括累加器）的所有寄存器（包括累加器）的l(xi)之之和，其中和，其中xi是在寄存器是在寄存器i中存储过的最中存储过的最大整数。大整数。2022-7-1985 of 158nREAD 1 c

30、ontinue:LOAD 2 LOAD 1 MULT 1 JGTZ pos STORE 2 WRITE =0 LOAD 3 JUMP endif SUB =1pos:LOAD 1 STORE 3 STORE 2 JUMP while LOAD 1 endwhile:WRITE 2 SUB =1 endif:HALT STORE 3while:LOAD 3 JGTZ continue JUMP endwhile2022-7-1986 of 158n(一一)均匀耗费下的时空复杂性：均匀耗费下的时空复杂性：1）时间复杂性：主要由循环中的各部分决）时间复杂性：主要由循环中的各部分决定的。程序共执行了定

31、的。程序共执行了n-1次循环，所以有次循环，所以有n-1次乘法和次乘法和n-1次减法、次减法、3(n-1)次次LOAD以及以及2(n-1)次次STORE，每个指令耗费一个，每个指令耗费一个单位时间，所需总时间为单位时间，所需总时间为 T(n)=7(n-1)=O(n)2）空间复杂性：此程序中共用了）空间复杂性：此程序中共用了4个寄存个寄存器，所以器，所以 S(n)=4=O(1)2022-7-1987 of 158nREAD 1 continue:LOAD 2 LOAD 1 MULT 1 JGTZ pos STORE 2 WRITE =0 LOAD 3 JUMP endif SUB =1pos:L

32、OAD 1 STORE 3 STORE 2 JUMP while LOAD 1 endwhile:WRITE 2 SUB =1 endif:HALT STORE 3while:LOAD 3 JGTZ continue JUMP endwhile2022-7-1988 of 1581）对数时间复杂性：对数时间复杂性：耗费耗费数据的长度之和数据的长度之和计算计算MULT 1的耗费的耗费l(c(0)+t(a)第第i 次循环次循环=l(c(0)+l(1)+l(c(1)=l(ni)+l(1)+l(n)=log|ni|+1+1+log|n|+1(i+1)logn2022-7-1989 of 158执行循环

33、总的耗费是执行循环总的耗费是)log(2nnOnnnlog2)2)(1(1111)1(loglog)1(niniinni2022-7-1990 of 158 READ 1 continue:LOAD 2 LOAD 1 MULT 1 JGTZ pos STORE 2 WRITE =0 LOAD 3 JUMP endif SUB =1pos:LOAD 1 STORE 3 STORE 2 JUMP while LOAD 1 endwhile:WRITE 2 SUB =1 endif:HALT STORE 3while:LOAD 3 JGTZ continue JUMP endwhile2022-7-

34、1991 of 158计算计算SUB-1的耗费的耗费l(c(0)+t(a)第第i 次循环次循环=l(c(0)+l(1)=l(n-i)+l(1)=log|n-i|+1+1(i+1)logn2022-7-1992 of 158结论结论 在对数时间复杂性中，我们只考虑循在对数时间复杂性中，我们只考虑循环中耗费最大的算术指令。环中耗费最大的算术指令。2）对数空间复杂性）对数空间复杂性 所有寄存器（包括累加器）的所有寄存器（包括累加器）的l(xi)之和，其中之和，其中xi是在寄存器是在寄存器i中存储中存储过的最大整数。过的最大整数。2022-7-1993 of 158 r0,r1,r2,r3中存储过的最

35、大数分别为中存储过的最大数分别为 nn,n,nn,n-1 所以所以S(n)=)log(log4)1()()(2)(30nnOnnnlnlnlxlnii2022-7-1994 of 158 均匀耗费标准均匀耗费标准 对数耗费标准对数耗费标准时间复杂性时间复杂性 O(n)O(n2logn)空间复杂性空间复杂性 O(1)O(nlogn)例例:写一个写一个RAM程序，它接受字母表程序，它接受字母表1，2上的一个语言，该语言包含所有由上的一个语言，该语言包含所有由同样多个同样多个1与与2组成的字符串该语言把组成的字符串该语言把每个输入符号读入寄存器每个输入符号读入寄存器r1中，中，2022-7-1995

36、 of 158 在寄存器在寄存器r2中记下到目前为止读入的中记下到目前为止读入的1的个数与的个数与2的个数之差的个数之差d。当读入结束。当读入结束符符0时，程序检查时，程序检查d是否为是否为0，若是，若是，则在只写输出带上写则在只写输出带上写1并停机。在此并停机。在此我们假设输入的符号只能是我们假设输入的符号只能是0，1和和2。2022-7-1996 of 158 int accept()int d=0;scanf(x);while(x!=0)if(x!=1)d-;else d+;scanf(x);if(d=0)return 1;内存内存r1存储每存储每个输入符号个输入符号x，r2存储差存储差

37、d，x=1时时d+;x=2时时d-;2022-7-1997 of 158LOAD =0d=0;STORE 2scanf(x);READ 1内存内存r1存存储每个输储每个输入符号入符号x，r2存储差存储差d，x=1时时d+;x=2时时d-;while(x!=0)while:LOAD 1JZERO endwhileif(x!=1)LOAD 1SUB =1JZERO addone2022-7-1998 of 158else d+;addone:LOAD 2ADD =1STORE 2内存内存r1存存储每个输储每个输入符号入符号x，r2存储差存储差d，x=1时时d+;x=2时时d-;2022-7-199

38、9 of 158 LOAD =0 addone:LOAD 2 STORE 2 ADD =1 READ 1 STORE 2 while:LOAD 1 endif:READ 1 JZERO endwhile JUMP while LOAD 1 endwhile:LOAD 2 SUB =1 JZERO output JZERO addone HALT LOAD 2 output:WRITE =1 SUB =1 HALT STORE 2 JUMP endif2022-7-19100 of 158n(一一)均匀耗费下的时空复杂性：均匀耗费下的时空复杂性：1）时间复杂性：）时间复杂性：T(n)=O(n)2

39、）空间复杂性：此程序中共用了）空间复杂性：此程序中共用了3个个寄存器，所以寄存器，所以 S(n)=3=O(1)2022-7-19101 of 1581）对数空间复杂性）对数空间复杂性 S(n)=)(loglog2)2()(2)(30nOnlnlxlii2022-7-19102 of 1582）对数时间复杂性：）对数时间复杂性：O(nlogn)2022-7-19103 of 158 均匀耗费标准均匀耗费标准 对数耗费标准对数耗费标准时间复杂性时间复杂性 O(n)O(nlogn)空间复杂性空间复杂性 O(1)O(logn)n总结：总结：1）同一个算法的时间或空间复杂性用两个）同一个算法的时间或空间

40、复杂性用两个标准度量的结果一般不同。标准度量的结果一般不同。2）何时用何种标准？若一个问题中遇到的）何时用何种标准？若一个问题中遇到的每一个数（包括中间结果在内），都可以每一个数（包括中间结果在内），都可以 存放在一个计算机字中，存放在一个计算机字中，2022-7-19104 of 158 则使用均匀耗费标准，否则用对数耗则使用均匀耗费标准，否则用对数耗费标准。费标准。3）不一定非要把类程序翻译成一个）不一定非要把类程序翻译成一个RAM程序。程序。4）RAM不是唯一的计算机模型，类似不是唯一的计算机模型，类似还有图灵机等计算机模型还有图灵机等计算机模型2022-7-19105 of 1585）

41、均匀耗费标准）均匀耗费标准 平均情况复杂性平均情况复杂性对数耗费标准对数耗费标准 最坏情况复杂性最坏情况复杂性6）除了特殊声明，一般还是采用基本）除了特殊声明，一般还是采用基本操作来衡量时空复杂性。操作来衡量时空复杂性。2022-7-19106 of 158递推方程及其求解递推方程及其求解定义：定义：给定一个数的序列给定一个数的序列H(0),H(1),H(n),把把H(n)和某些和某些H(i)(0in)联系起联系起来的一个等式就叫做一个递推关系。来的一个等式就叫做一个递推关系。例：河内例：河内(Hanoi)塔问题：塔问题：n个中空圆盘按个中空圆盘按其半径自大到小套在柱其半径自大到小套在柱A上，

42、如图所示。上，如图所示。若要把若要把柱柱A上的上的n个圆盘全部搬到柱个圆盘全部搬到柱C上，上，要求每次只能从一根柱上搬下一个圆盘放要求每次只能从一根柱上搬下一个圆盘放在另一根柱上，并且不允许大盘压在小盘在另一根柱上，并且不允许大盘压在小盘上，问至少要搬多少次？上，问至少要搬多少次？2022-7-19107 of 158ABC2022-7-19108 of 158解解 设设an为个为个n圆盘从圆盘从A柱搬柱搬到到C柱所需的最柱所需的最少次数。整个搬动过程可分为三个阶段：少次数。整个搬动过程可分为三个阶段：（1）将套到）将套到A柱上的柱上的n-1个圆盘个圆盘从从A柱上按柱上按要求搬要求搬到到B柱上

43、，搬动的最少次数为柱上，搬动的最少次数为an-1；（2）将套到）将套到A柱上最下面的圆盘搬到柱上最下面的圆盘搬到C柱柱上，搬动次数为上，搬动次数为1；（3）将套到）将套到B柱上的柱上的n-1个圆盘按要求搬到个圆盘按要求搬到C柱上，搬动的最少次数为柱上，搬动的最少次数为an-1。2022-7-19109 of 158 由加法原理知由加法原理知 an=2an-1+1 又又显然有显然有a1=1，所以有如下带有初值的，所以有如下带有初值的递推关系：递推关系：an=2an-1+1,a1=1n 这里面，也称这里面，也称a1=1为此递推关系的初为此递推关系的初始条件。始条件。2022-7-19110 of

44、158n常系数线性齐次递推关系的求解常系数线性齐次递推关系的求解 定义定义 设设c1,c2,ck是是k个常数，且个常数，且ck0，则递推关系则递推关系an=c1an-1+c2an-2+ckan-k nk (1)称为称为k阶常系数线性齐次递推关系。阶常系数线性齐次递推关系。如果一个数列代入递推关系（如果一个数列代入递推关系（1）中，）中，使得其对任意使得其对任意nk都成立，则称这个都成立，则称这个数列是递推关系（数列是递推关系（1）的一个解。）的一个解。2022-7-19111 of 158an=c1an-1+c2an-2+ckan-k(1)能表示出递推关系（能表示出递推关系（1）全部解的表达式

45、）全部解的表达式叫做递推关系叫做递推关系(1)的通解。若递推关系的的通解。若递推关系的一个解满足其初始条件，则称此解为这个一个解满足其初始条件，则称此解为这个递推关系的特解。一般的，递推关系（递推关系的特解。一般的，递推关系（1）的解有如下形式：的解有如下形式：an=xn (2)xn=c1xn-1+c2xn-2+ckxn-k (3)xk=c1xk-1+c2xk-2+ck 即即 xk-c1xk-1-c2xk-2-ck=0 (4)2022-7-19112 of 158an=c1an-1+c2an-2+ckan-k(1)xk-c1xk-1-c2xk-2-ck=0 (4)n定义定义 方程（方程（4）叫

46、做递推关系（）叫做递推关系（1）的特征方程，它的的特征方程，它的k个根个根q1,q2,qk（可能有重根）叫做该特征方程的特（可能有重根）叫做该特征方程的特征根。其中征根。其中qi(i=1,2,k)是复数。注：是复数。注：因为因为ck0，所以，所以0不是此递推关系的不是此递推关系的特征根。特征根。2022-7-19113 of 158特征方程 xk-c1xk-1-c2xk-2-ck=0n(一一)特征方程无重根：特征方程无重根：如果递推关系的如果递推关系的k个特征根个特征根q1,q2,qk互不相等，则互不相等，则an=A1q1n+A2q2n+Akqkn是递推关系的是递推关系的通解。其中通解。其中A

47、1,A2,Ak为任意常数。为任意常数。n(二二)特征方程有重根特征方程有重根:设设q是特征方程的是特征方程的l重根，则递推关系通解中对应于重根，则递推关系通解中对应于q的解为的解为 (A1+A2n+A3n2+Alnl-1)qn2022-7-19114 of 158n常系数线性非齐次递推关系的求解常系数线性非齐次递推关系的求解 定义定义 设设c1,c2,ck是是k个常数，且个常数，且ck0，f(n)是以非负整数是以非负整数n为自变量的实函数且为自变量的实函数且 f(n)0,则递推关系则递推关系an=c1an-1+c2an-2+ckan-k+f(n)nk (5)称为称为k阶常系数线性非齐次递推关系

48、对应阶常系数线性非齐次递推关系对应的齐次递推关系为的齐次递推关系为an=c1an-1+c2an-2+ckan-k （6）2022-7-19115 of 158定理定理:k 阶常系数线性非齐次递推关系（阶常系数线性非齐次递推关系（5）的通解是递推关系（的通解是递推关系（5）的特解加上其对）的特解加上其对应的齐次递推关系（应的齐次递推关系（6）的通解。）的通解。定理：定理：若若an和和an”分别是递推关系分别是递推关系 an=c1an-1+c2an-2+ckan-k+f1(n)和和 an=c1an-1+c2an-2+ckan-k+f2(n)的解，的解，则则 an=an+an”是递推关系是递推关系

49、an=c1an-1+c2an-2+ckan-k+f1(n)+f2(n)的解。的解。2022-7-19116 of 158f(n)满足条件满足条件 特解特解an的一般形式的一般形式cdn d不是特征方程的根不是特征方程的根 Bdn d是特征方程的是特征方程的m重根重根 Bdnnmcnt 1不是特征方程的根不是特征方程的根 Btnt+Bt-1nt-1+B1n+B0 1是特征方程的是特征方程的m重根重根 (Btnt+Bt-1nt-1+B1n+B0)nm其中其中c,d,t为已知常数，为已知常数，Bi为待定常数为待定常数2022-7-19117 of 158an=A1q1n+A2q2n+Akqkn例例

50、求递推关系求递推关系an=2an-1+3n-1(n1)满足初始条件满足初始条件a0=0 的解的解n解解 先求此递推关系所对应的齐次递推关先求此递推关系所对应的齐次递推关系系an=2an-1的通解。的通解。此递推关系的特征方程为此递推关系的特征方程为x-2=0 即即x=2 所以，此齐次递推关系的通解为所以，此齐次递推关系的通解为 an=A2n 再求原来的非齐次递推关系的一个特解，再求原来的非齐次递推关系的一个特解，因为因为3不是特征方程的根，由表，令不是特征方程的根，由表，令2022-7-19118 of 158cdn d不是特征方程的根 Bdn an=B3n-1，将其代入递推关系，得，将其代入

51、递推关系，得 B3n-1=an=2an-1+3n-1=2B3n-2+3n-1 即即 B=3 所以，这个非齐次方程递推关系的特解为所以，这个非齐次方程递推关系的特解为 an=33n-1=3n 此非齐次递推关系的通解为此非齐次递推关系的通解为 an=A2n+3n 由初始条件由初始条件a0=0，得，得 0=A20+30 从而从而 A=-1 故，原递推关系的解为故，原递推关系的解为 an=-2n+3n(n0)2022-7-19119 of 158an=A1q1n+A2q2n+Akqkn例：求递推关系例：求递推关系an=3an-1+23n-4n(n1)满足满足初始条件初始条件a0=4的解的解解解 首先，

52、易见此递推关系所对应的齐次递首先，易见此递推关系所对应的齐次递推关系为推关系为 an=3an-1 它的通解为它的通解为 an=A3n 其次，为求原递推关系的一个特解，可分其次，为求原递推关系的一个特解，可分别求递推关系别求递推关系 an=3an-1+23n ()和和 an=3an-1-4n ()的特解的特解an和和an”，2022-7-19120 of 158cdn d是特征方程的m重根 Bdnnm 由表由表,因为因为3是特征方程的是特征方程的1重根，所重根，所以令以令 an=B3nn1=Bn3n，代入式代入式()中得中得 Bn3n=3B(n-1)3n-1+23n 解得解得B=2，所以递推公式

53、，所以递推公式()有特解有特解 an=2n3n2022-7-19121 of 158cnt 1不是特征方程的根 Btnt+Bt-1nt-1+B1n+B0又由表，因为又由表，因为1不是特征方程的根，而不是特征方程的根，而t=1，所以令所以令 an”=B1n+B0 代入式代入式()中得中得 B1n+B0=3B1(n-1)+B0-4n 即即 B1n+B0=(3B1-4)n+(-3B1+3B0)比较上面关于比较上面关于n的多项式的系数，得到方程的多项式的系数，得到方程组组 B1=3B1-4 和和 B0=-3B1+3B0 解得解得 B1=2 ,B0=3 因此递推关系因此递推关系()有特解有特解 an”=

54、2n+3 2022-7-19122 of 158根据定理根据定理,原递推关系有特解原递推关系有特解 an+an”=2n3n+2n+3再由定理，原递推关系的通解为再由定理，原递推关系的通解为 an=A3n+2n3n+2n+3代入初始条件代入初始条件a0=4得得 4=A30+0+0+3 故故 A=1所以，原递推关系的解为所以，原递推关系的解为 an=3n+2n3n+2n+32022-7-19123 of 158请同学们改正书上请同学们改正书上34页的例页的例8原递推关系的解为原递推关系的解为 xn=2n n2n+1 (n0)求解递推关系的其他方法求解递推关系的其他方法（1）迭代归纳法）迭代归纳法例：求解递推关系例：求解递推关系 an=（n+2)an-1 a0=22022-7-19124 of 158 (2)将非线性递推关系变成线性递推关系将非线性递推关系变成线性递推关系例：求解递推关系例：求解递推关系an2=3an-12-1 a0=1例：求解递推关系例：求解递推关系an=2an-12 a0=1