计算机问题求解：分治法与递归

计算机问题求解

–

论题2-3

分治法与递归MergesortRevisited问题1:这个算法究竟是如何“排”序的？5 2 4 7 1 3 2 65 2 4 71 3 2 6DivideDividefurther,until…conquer问题2：人的思维“分而治之”如何变为算法策略的呢？问题3：如何考虑分治算法的代价？递归代价与非递归代价导出递归式两次递归，理想情况下每次问题规模是原来的一半。非递归开销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：跨中点的部分如何计算？非递归代价：常量递归，理想状况下问题规模是原来的一半。非递归代价：线性非递归代价：常量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