計算機問題求解：分治法與遞歸

計算機問題求解

–

論題2-3

分治法與遞歸MergesortRevisited問題1:這個算法究竟是如何“排”序的？5 2 4 7 1 3 2 65 2 4 71 3 2 6DivideDividefurther,until…conquer問題2：人的思維“分而治之”如何變?yōu)樗惴ú呗缘哪?？問題3：如何考慮分治算法的代價？遞歸代價與非遞歸代價導出遞歸式兩次遞歸，理想情況下每次問題規(guī)模是原來的一半。非遞歸開銷ncn

log

n確實比插入排序效率高。這里似乎假設n是2的整次冪，在我們涉及的大多數情況下，這不影響結果。問題4：書上的投資回報問題是怎樣被轉化為最大子數組問題的？Maximumsubarray簡單的遍歷所有可能的子序列MaxSum=0;

for(i=0;i<N;i++){ThisSum=0;

for(j=i;j<N;j++){

ThisSum+=A[j];if(ThisSum>MaxSum)MaxSum=ThisSum;}}returnMaxSum;thesequencei=0i=1i=2i=n-1jinO(n2)下面的過程遍歷的順序為：(0,0),(0,1),…,(0,n-1);(1,1),(1,2),…,(1,n-1),……(n-2,n-2),(n-2,n-1),(n-1,n-1)用分治法解最大子數組問題Part1Part2thesubwithlargestsummaybein:Part1Part2or:Part1Part2recursionThelargestistheresult問題5：跨中點的部分如何計算？非遞歸代價：常量遞歸，理想狀況下問題規(guī)模是原來的一半。非遞歸代價：線性非遞歸代價：常量O(n

log

n)矩陣乘法：似乎非得

(n3)1個n階方陣相乘的問題可以分解為8個n/2階方陣相乘的子問題。仍然是立方復雜度問題6：決定上面的遞歸代價比較大的原因是什么？問題7：你能否描述Strassen方法的基本思想？復雜的組合為了減少一次乘法諸Si只需通過加減法計算這個算法曾經引起轟動問題8：你對于這個結果是否有感性認識？問題9：為什么降低子問題個數會導致復雜度的階下降？遞歸樹

T(size)nonrecursivecost對應于T(n)=T(n/2)+T(n/2)+n的遞歸樹T(n)nT(n/4)n/4T(n/4)n/4T(n/4)n/4T(n/4)n/4T(n/2)n/2T(n/2)n/2對應于分治法的遞歸樹方程divide-and-conquer:T(n)=aT(n/b)+f(n)Afterkthexpansion:T(n)=3T(

n/4)+(n2)cn2T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)c((1/16)n)2c((1/16)n)2…………c(?n)2c(?n)2c(?n)2log4ncn2…Total:

(n2)Note:c((1/16)n)2c((1/16)n)2c((1/16)n)2…………T(1)T(n)=aT(n/b)+f(n)f(n)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)f(n/b2)f(n/b2)f(n/b2)f(n/b2)f(n/b2)f(n/b2)f(n/b2)f(n/b2)f(n/b2)…………f(n/b)f(n/b)f(n/b)logbnf(n)…Note:aaTotal?…SolvingtheDivide-and-ConquerT(n)=aT(n/b)+f(n)作為一種典型的分治算法遞歸式:Letbase-casesoccuratdepthD(leaf),thenn/bD=1,thatisD=lg(n)/lg(b)LetthenumberofleavesofthetreebeL,thenL=aD,thatisL=a(lg(n)/lg(b)).Byalittlealgebra:L=nlg(a)/lg(b),lg(a)/lg(b)=logba因此，這個值決定了樹的“胖”度。Divide-and-Conquer:theSolutionTherecursiontreehasdepthD=lg(n)/lg(c),sothereareaboutthatmanyrow-sums.The0throw-sumisf(n),thenonrecursivecostoftheroot.TheDthrow-sumis,assumingbasecasescost1,or(

)inanyevent.Thesolutionofdivide-and-conquerequationisthenon-recursivecostsofallnodesinthetree,whichisthesumoftherow-sums.SolutionbyRow-sums[LittleMasterTheorem]Row-sumsdecidethesolutionoftheequationfordivide-and-conquer:Increasinggeometricseries:T(n)

(nE)Constant:T(n)

(f(n)logn)Decreasinggeometricseries:T(n)

(f(n))Thiscanbegeneralizedtogetaresultnotusingexplicitlyrow-sums.MasterTheorem對簡單的分治法解矩陣相乘，logba

=3。問題10：在比較兩個函數大小時，是什么意思？Polynomiallylarger/smallerUsingMasterTheoremUsingMasterTheoremMaster定理的條件有空隙T(n)=2T(n/2)+nlgna=2,b=2,logba=1,f(n)=nlgnWehavef(n)=(n1),butno>0satisfiesf(n)=(n1+),sincelgngrowsslowerthatn

foranysmallpositive.So,case3doesn’tapply.However,neithercase2appli