算法设计与分析不全第一

1、2.3.1 算法的复杂性1.7 对偶与范式2 of 158符号1.7 对偶与范式3 of 158符号1.7 对偶与范式4 of 158符号n2 对数对数logn=log2n lgn=log10n lg2=0.3011.7 对偶与范式5 of 158符号n证明：证明：nbalognbbablogloganbbblogloganbbbloglog)(abnlog1.7 对偶与范式6 of 158符号nlogbN=logaN/logabnlogeN=lnN ne=2.71828nlogab=1/logba1.7 对偶与范式7 of 158符号1.7 对偶与范式8 of 158符号1.7 对偶与范式9

2、 of 158符号1.7 对偶与范式10 of 158符号n调和级数调和级数nkOnk1) 1 (ln11.7 对偶与范式11 of 1581、衡量算法优劣的标准：时空复杂性、衡量算法优劣的标准：时空复杂性2、问题规模：与问题相关的整数量，、问题规模：与问题相关的整数量，它可以衡量问题的规模并表示输入数它可以衡量问题的规模并表示输入数据量的尺度。也称为问题尺度据量的尺度。也称为问题尺度3、算法的时间复杂性：处理一个尺度、算法的时间复杂性：处理一个尺度为为n的输入，算法所需要的的输入，算法所需要的时间时间，记，记为为T(n)1.7 对偶与范式12 of 1583、算法的时间复杂性：处理一个尺度、

3、算法的时间复杂性：处理一个尺度为为n的输入，算法所需要的输入，算法所需要的执行次数的执行次数（或执行的步数）（或执行的步数），记为，记为T(n)1.7 对偶与范式13 of 1584、渐进时间复杂性：、渐进时间复杂性：当问题的尺度增加时，时间复杂性的当问题的尺度增加时，时间复杂性的极限极限5、算法的空间复杂性：、算法的空间复杂性：处理一个尺度为处理一个尺度为n的输入，算法所需要的输入，算法所需要的空间数，记为的空间数，记为S(n)1.7 对偶与范式14 of 1586、渐进空间复杂性：、渐进空间复杂性：当问题的尺度增加时，空间复杂性的当问题的尺度增加时，空间复杂性的极限极限7、时空综合复杂性、

4、时空综合复杂性 T(n)S(n)1.7 对偶与范式15 of 1588、算法复杂性的阶、算法复杂性的阶处理尺度为处理尺度为n的输入，需要执行的输入，需要执行Cn2次次,则算法复杂性是则算法复杂性是O(n2)，读作，读作“n2阶阶”1.7 对偶与范式16 of 1581.7 对偶与范式17 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) 1.7 对偶与范式18 of 158例例1 0.25n2=O(n2) （相差常数因子）（相差常数因子） 0.73n2O(n) （阶不

5、等）（阶不等） n(n+1)/3=O(n2) （相差低阶项）（相差低阶项） 5n4 6n2+1=O(n4) (相差低阶项和相差低阶项和常数因子常数因子)1.7 对偶与范式19 of 158等式等式 0.75n2=O(n)何时成立？何时成立？永不成立永不成立等式等式3n1/2=O(n)在在n=9时成立吗？时成立吗？n=9时，虽然两边值相等，但等式不成时，虽然两边值相等，但等式不成立立1.7 对偶与范式20 of 158n例例2： 60n2+5n+1 n60n2+5n+1 60n2+5n2+n2 =66n2 对于对于n 1n所以所以 60n2+5n+1 =O(n2)n又又60n2+5n+1 60n

6、2 对于对于n 1n所以所以 60n2+5n+1 = (n2)n综上综上 60n2+5n+1 = (n2)1.7 对偶与范式21 of 1581.7 对偶与范式22 of 158n例例4： 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 = ?1.7 对偶与范式23 of 158n又又1+2+n nnn) 1(.222.22nnnn 221nn4222nnn1.7 对偶与范式24 of 158n所以所以 1+2+n = (n2)n综上综上 1

7、+2+n = (n2)n练习：给出练习：给出1k+2k+nk 的的 表示表示n作业：作业：给出给出logn!的的 表示表示1.7 对偶与范式25 of 158n求上界的方法求上界的方法1.7 对偶与范式26 of 1581.7 对偶与范式27 of 1581.7 对偶与范式28 of 1581.7 对偶与范式29 of 158n求下界的方法：求下界的方法：n缩小法缩小法1.7 对偶与范式30 of 158n求复杂性函数阶的极限方法求复杂性函数阶的极限方法例如，f(n)=n2/4, g(n)=n2, 则n2/4 =(n2)f(n)=logn, g(n)=n, 则logn=O(n);()()();

8、()()(0);()()(0)()(limgfngnfsgOfngnfsgfngnfssngnfn则的阶高，比说明时，当则的阶低，比说明时，当则同阶，和说明时，当若1.7 对偶与范式31 of 158n渐近分析渐近分析在渐近意义下(即问题的规模n充分大时)，对算法进行优劣分类。例：例：对问题对问题P P有算法有算法A A和算法和算法B B，它们的时间复杂，它们的时间复杂性分别为性分别为T TA A(n)=3n(n)=3n2 2，T TB B(n)=25n(n)=25n。对不同的。对不同的n n比较有比较有 n 7 8 9 TA(n) 147 192 243 TB(n) 175 200 225

9、可见，n8时算法B会越来越好于算法A即n较大时的性能是重要的，因此渐近分析是合理的。1.7 对偶与范式32 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)的含义？的含义？计算时间由一个常数（零次多项式）来限界计算时间由一个常数（零次多项式）来限界1.7 对偶与范式33 of 158指数

10、时间指数时间一个算法的时间复杂性如果是一个算法的时间复杂性如果是O(2n)，则称，则称此算法需要指数时间。此算法需要指数时间。多项式时间多项式时间一个算法的时间复杂性如果是一个算法的时间复杂性如果是O(nk)(k为有为有理数），则称此算法需要多项式时间。理数），则称此算法需要多项式时间。有效算法有效算法以多项式时间为限界的算法称为有效算法。以多项式时间为限界的算法称为有效算法。1.7 对偶与范式34 of 158Time to FinishInput Size (n)O(nx)O(n)O(1)O(n lg n)O(an)1.7 对偶与范式35 of 1581.7 对偶与范式36 of 1581

11、.7 对偶与范式37 of 158例n例：算法例：算法A1,A2的时间复杂性分别是的时间复杂性分别是n,2n,设设100s是一个单位时间，求是一个单位时间，求A1,A2在在1s内能处理的问题规模。内能处理的问题规模。n已知已知lg2=0.3011.7 对偶与范式38 of 158作业nP22- 61.7 对偶与范式39 of 158复杂性的基本概念n有效算法：有效算法：以多项式时间为限界的算法。以多项式时间为限界的算法。n按算法的时间复杂性，可以把问题分为按算法的时间复杂性，可以把问题分为3类：类：1）p类问题类问题能以多项式时间为界的算法解决的问题能以多项式时间为界的算法解决的问题1.7 对

12、偶与范式40 of 1582）NP类问题：已知的最好算法是以非类问题：已知的最好算法是以非多项式时间为界的问题。多项式时间为界的问题。3）写不出算法的问题。）写不出算法的问题。实际上可计算的问题：实际上可计算的问题： 多项式时间可解的问题多项式时间可解的问题1.7 对偶与范式41 of 158有时，算法中基本操作重复执行的次数会有时，算法中基本操作重复执行的次数会随问题的输入数据集不同而不同。随问题的输入数据集不同而不同。比如：冒泡法排序比如：冒泡法排序n个整数个整数1）当原始数据是从小到大有序排列时，则）当原始数据是从小到大有序排列时，则基本操作（交换序列中相邻的两个整数）基本操作（交换序列

13、中相邻的两个整数）的执行次数为的执行次数为01.7 对偶与范式42 of 1582）当原始数据是从大到小有序排列时，）当原始数据是从大到小有序排列时，基本操作的执行次数为基本操作的执行次数为n(n-1)/2n解决方法：解决方法：1）求平均情况的时间复杂性）求平均情况的时间复杂性 即考虑算法对所有可能的输入数据集的期即考虑算法对所有可能的输入数据集的期望值，此时对应的时间复杂性为算法的平望值，此时对应的时间复杂性为算法的平均时间复杂性。均时间复杂性。1.7 对偶与范式43 of 158n2）求最坏情况的时间复杂性）求最坏情况的时间复杂性 即分析最坏情况以估算算法执行时间即分析最坏情况以估算算法执

14、行时间的一个上界。的一个上界。1.7 对偶与范式44 of 158两点说明：两点说明：1）用基本操作重复执行的次数作为算）用基本操作重复执行的次数作为算法的时间复杂性比较粗略法的时间复杂性比较粗略2）在实践中我们可以把算法的事前分）在实践中我们可以把算法的事前分析和事后统计两种方法结合起来使用。析和事后统计两种方法结合起来使用。1.7 对偶与范式45 of 158例：若上机运行了一个问题尺度为例：若上机运行了一个问题尺度为10的算法，执行时间为的算法，执行时间为6ms，并且算法，并且算法的时间复杂性为的时间复杂性为T(n)=O(n2)，则可以，则可以估算问题尺度为估算问题尺度为21时，所需时间

15、大致时，所需时间大致为为 （21/10)26ms26.5ms2.3.2随机存取机随机存取机(RAM)1.7 对偶与范式47 of 158nRAM的结构示意图的结构示意图 x1x2只读输入带程序存储器指令计数器y1y2只写输出带累加器内存储器r0r1r21.7 对偶与范式48 of 1581. RAM的组成的组成1）只读输入带：被划分成一系列方格，每）只读输入带：被划分成一系列方格，每个方格可存放任意大小的整数。每当从输个方格可存放任意大小的整数。每当从输入带中读出一个数据时，带头就自动向右入带中读出一个数据时，带头就自动向右移动一格。初始时，其上依次存放有算法移动一格。初始时，其上依次存放有算

16、法运行所需的全部初始数据。运行所需的全部初始数据。1.7 对偶与范式49 of 1582）只写输出带：被划分成一系列方格，）只写输出带：被划分成一系列方格，每个方格可存放任意大小的整数。每每个方格可存放任意大小的整数。每输出一个数据，带头就自动向右移动输出一个数据，带头就自动向右移动一格。初始时，其上所有方格为空。一格。初始时，其上所有方格为空。3）程序存储器：只存放程序）程序存储器：只存放程序4）指令计数器：控制程序走向，即确）指令计数器：控制程序走向，即确定下一条要执行的指令。定下一条要执行的指令。1.7 对偶与范式50 of 1585）内存储器：由一系列寄存器）内存储器：由一系列寄存器r

17、0,r1,r2,组组成，每个寄存器都能存放一个任意大小的成，每个寄存器都能存放一个任意大小的整数。寄存器的个数是任意的。其中，第整数。寄存器的个数是任意的。其中，第一个寄存器一个寄存器r0称为累加器，所有的运算都称为累加器，所有的运算都在其中进行。在其中进行。1.7 对偶与范式51 of 1582. RAM的指令系统的指令系统 一条一条RAM指令一般由操作码和操作指令一般由操作码和操作数组成。数组成。 例如：例如： 指令指令 STORE i 表示把累加表示把累加器中的内容送入内存器中的内容送入内存ri中中 其中其中STORE 是操作码：操作定义符，是操作码：操作定义符，指明操作意义指明操作意义 i是操作数：指示操作对象是操作数：指示操