算法設(shè)計(jì)與分析5

1、算法設(shè)計(jì)與分析基礎(chǔ)算法設(shè)計(jì)與分析基礎(chǔ) Introduction to the Design and Analysis of Algorithms第五章第五章 減治法減治法Decrease and ConquerDecrease and Conquer12021/8/6原問題原問題(規(guī)模規(guī)模子問題子問題(規(guī)模規(guī)模子問題子問題(規(guī)模規(guī)模原問題原問題 (規(guī)模規(guī)模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 頂點(diǎn)進(jìn)棧的線性序列：頂點(diǎn)進(jìn)棧的線性序列：頂點(diǎn)退棧的線性序列：頂點(diǎn)退棧的線性序列：()1 / / /0/( )/)0(DFSRecursion vertexcountcountMark vcount

3、eachvertexadjacent tvwvDFSRfordoiftecursion whvoMarkisit vctwenoun全全局局變變量量，初初始始化化為為0 0: :已已訪訪問問按按訪訪問問序序標(biāo)標(biāo)記記頂頂點(diǎn)點(diǎn)/ / / / /0GvcouGntV輸輸入入: :給給定定圖圖的的一一個(gè)個(gè)起起始始頂頂點(diǎn)點(diǎn)輸輸出出: :圖圖頂頂點(diǎn)點(diǎn)，按按訪訪問問順順序序用用連連續(xù)續(xù)整整數(shù)數(shù)標(biāo)標(biāo)記記中中標(biāo)標(biāo)記記為為 的的頂頂點(diǎn)點(diǎn)，表表示示未未訪訪問問(,)0( )( )( ) 0( ),1,/( )( )/DFS GraphVertexcountvirst vInitialize SisEmpty SFA

4、LSExeachvertexadjacent toMarkwhilefordGvPush vPop Swvirst wcountcountMark wcoifthewxPounptonSvt頂頂點(diǎn)點(diǎn)標(biāo)標(biāo)號(hào)號(hào)棧棧初初始始化化為為空空起起始始頂頂點(diǎn)點(diǎn)入入棧棧棧棧頂頂頂頂點(diǎn)點(diǎn)出出棧棧()ush w(2)(2)(3)(2)(3)(2)abcdecdcfabeaecdfbef 表表頭頭頂頂點(diǎn)點(diǎn)邊邊數(shù)數(shù) 入隊(duì)，開始入隊(duì)，開始BFS出隊(duì)，出隊(duì)，A的鄰接的鄰接頂點(diǎn)頂點(diǎn)入隊(duì)入隊(duì)出隊(duì)，出隊(duì)，C的鄰接的鄰接頂點(diǎn)頂點(diǎn)入隊(duì)入隊(duì)(,)0( )( )( ) 0( ),( )( )/, /BFS GraphVertexcou

5、ntvirst vInitialize QisEmpty QFGvEnqueue vvDequeue QwALSExeachvertexadjacent toMark wvirst wcounwtMark wcouQhilnefordoifthetxnEn頂頂點(diǎn)點(diǎn)標(biāo)標(biāo)號(hào)號(hào)隊(duì)隊(duì)列列初初始始化化為為空空起起始始頂頂點(diǎn)點(diǎn)入入隊(duì)隊(duì)隊(duì)隊(duì)頭頭頂頂點(diǎn)點(diǎn)出出隊(duì)隊(duì))(queue w/,/0GVcouGVnvtE輸輸入入: :圖圖和和起起始始頂頂點(diǎn)點(diǎn)輸輸出出: :圖圖頂頂點(diǎn)點(diǎn)，按按訪訪問問順順序序用用連連續(xù)續(xù)整整數(shù)數(shù)標(biāo)標(biāo)記記中中標(biāo)標(biāo)記記為為 的的頂頂點(diǎn)點(diǎn): : 未未訪訪問問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 中中值值分分裂裂點(diǎn)點(diǎn)lr A l A r A xx tA x( )() A lrllA rA lA