算法设计与分析5

1、算法设计与分析基础算法设计与分析基础 Introduction to the Design and Analysis of Algorithms第五章第五章 减治法减治法Decrease and ConquerDecrease and Conquer12021/8/6原问题原问题(规模规模子问题子问题(规模规模子问题子问题(规模规模原问题原问题 (规模规模8968 90 29 34 1745 8990 29 34 1745 68 8929 34 1745 68 89 902934 1745 68 84569 901729 34 45 68 89 9017 29 34 45 6890293418

2、 89 907jjjjjVVVVVVj0.1( )/(1)1,(0 )11 /01:1nVA iInsertionSort AinjijA jVA jA jA jVVfortodowhi enjla djj 插插入入元元素素后后移移限限位位11( )11( )nbestiTnnn 11121011( )112.(1)(1)()2ninworstijiTninn nn 22( )/4()avgTnnn 顶点进栈的线性序列：顶点进栈的线性序列：顶点退栈的线性序列：顶点退栈的线性序列：()1 / / /0/( )/)0(DFSRecursion vertexcountcountMark vcount

3、eachvertexadjacent tvwvDFSRfordoiftecursion whvoMarkisit vctwenoun全全局局变变量量，初初始始化化为为0 0: :已已访访问问按按访访问问序序标标记记顶顶点点/ / / / /0GvcouGntV输输入入: :给给定定图图的的一一个个起起始始顶顶点点输输出出: :图图顶顶点点，按按访访问问顺顺序序用用连连续续整整数数标标记记中中标标记记为为 的的顶顶点点，表表示示未未访访问问(,)0( )( )( ) 0( ),1,/( )( )/DFS GraphVertexcountvirst vInitialize SisEmpty SFA

4、LSExeachvertexadjacent toMarkwhilefordGvPush vPop Swvirst wcountcountMark wcoifthewxPounptonSvt顶顶点点标标号号栈栈初初始始化化为为空空起起始始顶顶点点入入栈栈栈栈顶顶顶顶点点出出栈栈()ush w(2)(2)(3)(2)(3)(2)abcdecdcfabeaecdfbef 表表头头顶顶点点边边数数 入队，开始入队，开始BFS出队，出队，A的邻接的邻接顶点顶点入队入队出队，出队，C的邻接的邻接顶点顶点入队入队(,)0( )( )( ) 0( ),( )( )/, /BFS GraphVertexcou

5、ntvirst vInitialize QisEmpty QFGvEnqueue vvDequeue QwALSExeachvertexadjacent toMark wvirst wcounwtMark wcouQhilnefordoifthetxnEn顶顶点点标标号号队队列列初初始始化化为为空空起起始始顶顶点点入入队队队队头头顶顶点点出出队队)(queue w/,/0GVcouGVnvtE输输入入: :图图和和起起始始顶顶点点输输出出: :图图顶顶点点，按按访访问问顺顺序序用用连连续续整整数数标标记记中中标标记记为为 的的顶顶点点: : 未未访访问问DFSDFS退栈线性序列退栈线性序列：7 5 4 6 2 3 1 （或（或 7 5 4 3 6 2 1）退栈线性逆序退栈线性逆序：12, .,naaa012.2nnnnnnCCCC1:( )01:( )(/ 2 )1nT nnT nTn 2( )log(log )T nnn22nmnm122mnmnm 22nmnm122mnmnm / 2kn /2 .1 1.1 PartitionPartitions knA sA ssAA snAA sAs 中中值值分分裂裂点点lr A l A r A xx tA x( )() A lrllA rA lA