算法效率分析基础课件

1、2作者：（美）作者：（美）Anany Levitin 译者：潘彦译者：潘彦出版社：清华大学出版社：清华大学丛书名：国外经典教材丛书名：国外经典教材 计算机计算机 科学与技术科学与技术4567( )( )T ntC n 忽略了非基本忽略了非基本操作执行时间操作执行时间为什么用约等于符号？为什么用约等于符号？81( )(1)2C nn n( )( )T ntC n 221111( )(1)2222C nn nnnn （n 不是太小如不是太小如 n = 100）221(2 )(2 )(2 )2()1( )(4)2nTntCnT ntC nn倍倍不考虑每个操作步在机器上具体的执行时间不考虑每个操作步在

2、机器上具体的执行时间 t ，则时间耗费即为：，则时间耗费即为：( )( )T nC n 时间耗费即为基本操作数，为输入规模时间耗费即为基本操作数，为输入规模n的函数。的函数。n的一次、二次函数分别称线性、二次增长率。的一次、二次函数分别称线性、二次增长率。2n 称指数增长率。称指数增长率。9增长函数表：对于算法分析具有重要意义的函数值（近似值）增长函数表：对于算法分析具有重要意义的函数值（近似值） 指指数数增增长长 一个需要指数级操作次数的算法只能用来解决规模非常小的问题。一个需要指数级操作次数的算法只能用来解决规模非常小的问题。10111213( )(1)(1 2 .)(1)(12(.)(1

3、)1)2(1)/2,1(1)(1),02avgCnpp n nnnpninppppnpnnnnpnnnpp nnpnp 1415222(),1005(),0.5 (1)()nO nnO nn nO n 323242(),0.00001(),1()nO nnO nnnO n 16323242(),0.00001(),1()nnnnnnn 20.5 (1)()n nn 0:( )( )nnT ncg n n0n( )cg n( )T n规模规模增长函数增长函数n0 之前之前情况无情况无关紧要关紧要( )( ( )T nO g n 最差效率分析最差效率分析1721005()nO n 2( )1005

4、100(5)101101T nnnnnnn 当当220( )101( )( ),( ),()5,g nnT nccg nT nO nn 证证毕毕2( )10051005 (1)105105T nnnnnnn 当当022( )1005,( )105,( )(1,),( )()T nng nnT ncncg nT nO n证证毕毕n0n( )cg n( )T n规模规模增长函数增长函数n0 之前之前情况无情况无关紧要关紧要( )( ( )T ng n 最佳效率分析最佳效率分析0:( )( )nnT ncg n 18012:( )( )( )nnc g nT nc g n n0n1( )c g n(

5、 )T n规模规模增长函数增长函数n0 之前之前情况无情况无关紧要关紧要( )( ( )T ng n 2( )c g n20.5 (1)()n nn 222220.5 (1)0.50.50.5()n nnnncOnn 22222100.5 (1)0.50.50.50.5(2)0.25(.5)nn nnnnnwhile nnnnc 0n 1200.25,0.52ccn 19( )( ( ),( )( ( ),( )( ( )T nO g ng nO h nT nO h n 若若则则: :( )( ),0,( )( ( )T nO Kg nKT nO g n 若若则则: :11221212( )(

6、 ),( )( )( )( )( )( )T nO g nT nO g nT n T nO g n g n 若若则则11221212( )( ),( )( )( )( )( ),( )T nO g nT nO gnT nT nO max g ngn 若若则则2011221212( )( ),( )( )( )( )( ),( )T nO g nT nO gnT nT nO max g ngn 若若则则111111( )( )( ),)T nc g nT nO g nnn 对对于于所所有有有有：222222( )( )( ),)T nc g nT nO g nnn 对对于于所所有有有有：1211

7、22123121211223132213312,( )( )( )( )( )( )2( ),( )()()( ),( ),( )( )g ng nmcmax ccnmax nnc g nc g nc g nc g nccmaxT nT nO maxg ng ng n g nax g ng nc 取取且且则则：21:( )( ( )(0()( ):( )( ( )( )( ):( )( ( )()l)( )im(nT nO g nT ng nT ng nTcT nng nT ng nT ng ng n 比比增增长长慢慢与与增增长长相相同同比比增增长长快快不不存存在在: :该该法法不不适适用用例

8、例1：比较：比较0.5n(n-1)和和n2的增长率。（或证明的增长率。（或证明: 0.5n(n-1)(n2)）22220.5 (1)1111limlimlim(1)2221(1)()2nnnn nnnnnnn nn22例例2：2log nn比比较较和和的的增增长长次次数数。2222log(log)limlim()()1loglimlim022log1nnnnnnnenennnn 常常数数罗罗必必塔塔法法则则例例3：!2nn比比较较和和的的增增长长次次数数。2( )!limlim()22lim2lim2()22nnnnnnnnnnnnnnennnnee 史史特特林林公公式式2324本算法每个数组

9、元素都要本算法每个数组元素都要进行一次比较，故不区分进行一次比较，故不区分最优、最差和平均效率。最优、最差和平均效率。2511( )1( )1niC nnn 结论结论：本算法具有线性增长率：本算法具有线性增长率261221111121001()111111112(1)()22112111(1);2211lglgmmmmmiiiiiii li ki li li lmi lm lninkkkkkinnnininiinicacaababmlinn nnninnkaaaaaaainni 21121 22 22(1)22ninninn 2701221nn 28 222000220202122120( )

10、(1)(1)(1)1(1)1(1)2211111(1)1(1)(1)1(2)(1)2(1)21)()2(2)12nnnworstiiinninj iniiCnninnnnnninnnninnnnnn 20(1)(1)(2)(3)1112(1)(1)2ninnnnnin n 2902011,1nnjji jiiijBBMAAAB 如果是非方阵，只需改变行列循环如果是非方阵，只需改变行列循环变量的范围即可。本例均为变量的范围即可。本例均为n-1301111110000001123120030( )11)1(nnnnnnijijijnnkniinCnnnnnn 312logbn 向向上上取取整整，不

11、不小小于于该该实实数数的的整整数数/2n2bmaxn 22logl(loog )gbnnn 一点说明一点说明：考虑对数换底公式：考虑对数换底公式logloglogaabbnn 常常数数因此，当我们分析增长率时，忽略对数因此，当我们分析增长率时，忽略对数的底，简单写成的底，简单写成logn320n (1)4x ( )2(1),0 x nnn( )(1),1(0)0 x nx nnnx 33,( )(1(0)01)nnx nx nx 初初始始条条件件(1)( ),02n nx nn (1)2(1)(12)(1)2)22x nnx nnnnn nn n 0(01)(0)02x ( )(1)/2x n

12、n nc不包括初始条件不包括初始条件34( )2 (1)1,1(1)1x nx nnx (1)1(2)2 (1)12 113(3)2 (2)12 317(4)2 (3)12 7115(5)2 (4)12 15131xxxxxxxxx (10),2nx nn 12 (1)12(21)1221( )nnx nx n 右右端端左左端端验证：验证：代入法代入法方法评价：有时候很难从方法评价：有时候很难从序列前几项中找到通项！序列前几项中找到通项！35( )(1,1(0)0)xnxnnnx (1)(2)(1)(2)(3)( )(1)(22)(1)()(1)()(1)(3)(22)()1)x nx nx

13、nnx nnx nnknkx nnnx nx nnnnnnnkxn 根据初始条件根据初始条件(n=0)要求：要求：, 上式变为：上式变为：(0)121( )(1)2xxnnnn 该法所得通项是该法所得通项是直接由递推式推直接由递推式推出来的，故无需出来的，故无需验证。验证。3612( )(1)(2)(aax nx nx nf n 2120qa qa 12qq 1122( )nnx nc qc q c1和和c2为待定常数为待定常数3712qqq1212( )()nnnx nc qc nqcc n q c1和和c2为待定常数为待定常数( )6 (1)9 (2)0(0)0,(1)3x nx nx n

14、xx 2212690,(3)0,3qqqqqq 1212( )33()3nnnx ncc ncc n c1和和c2为待定常数为待定常数012111220(0)( )330)3(1)(1)31nxcx ncnccxcc 38( )6 (1)9 (240)(0)0,(1)3x nx nx nxx 1212( )33()3nnnx ncc ncc n c1和和c2为待定常数为待定常数( )x nc 6941cccc12( )331nnx nncc c1和和c2为待定常数为待定常数0012111121212(0)303110(1)31 31331135/3xccccccccxc 5( )3313nnx

15、 nn 3912( )(1)(2)()kx nx nxaaaf nnx nk ( )0f n 12101210kkkkkqa qa qaqa q 121232123112123( )(1)0( )(1)(2)0( )(1)(1:2:3:0020)(3)0qaqa qx na x nx na x na x nx na x na x naqa qaakkqx nak 401122( )nnnkkx nc qc qc q ck 为待定常数为待定常数 011111(i-1)r(k-(i-1)-r)=(k)-(1i+1r)+11( )niinrnii ri ri rinnkkx nc qcqc ncnc

16、nqcqc q 前前面面个个非非重重根根中中间间 个个重重根根后后面面个个非非重重根根12: (1) ( ) 11ii riii rrirqqqqq 个个41110121( )ttttx np np np npn 0111221230:( )1:( )2:( )tx np nptx np nptx np np np ( )nf nab ( ),nx ncbc 待待定定p 为待定系数为待定系数( ),encx ncn b 待待定定424( )5 (1)6 (2)(0)04,(1)20nx nx nx nxx 212560(2)(3)02,3qqqqqq 112212( )( 2)( 3)nnnn

17、x nc qc qcc( )4 ,nnx nc bcc 待待定定125644442 4nnnnccc 431244442 4564444241610321424216854868nnnnnnnnccccccccccc 非齐次递推方程的一个特解为：非齐次递推方程的一个特解为：4）非齐次递推方程的通解：（定理）非齐次递推方程的通解：（定理2）2( )416 44nnnx nc 212( )( 2)( 3)4nnnx ncc 非非齐齐次次特特解解齐齐次次通通解解5）求满足初始条件的非齐次递推方程的解（特解）：）求满足初始条件的非齐次递推方程的解（特解）： 非齐次递推方程的通解中代入初始条件非齐次递推

18、方程的通解中代入初始条件x(0)=0, x(1)=0000 21212111 2121212(0)( 2)( 3)4160(1)( 2)( 3)423640112,96xccccxcccccc 2( )112( 2)96( 3)4nnnx n 4412010( )niiinA xa xa xxa xa 012,naaaa451121( )2 (1)1(1)11nnaaa na naa 序列的下标表示法序列的下标表示法序列的函数表示法序列的函数表示法解：解：1）定义生成函数：）定义生成函数：2）利用递推式化简：）利用递推式化简：1212( )nnA xa xa xa x 123123231212( )(2)22nnnnA xa xa xa xa xA xxxa xa xa 2132211311122(12 ) ( )()()(2)nnnaaaax A xxxxxaaa 121nnaa 12(12 ) (11)nx A xxxxxx 麦克劳林