Divide-and-conquer algorithms

← Back to document page

Chapter2Divide-and-conqueralgorithmsThed ivide-and-conquerstrategysolvesa ,inthreedifferentplaces:inthepartitionin gofproblemsintosubproblems;attheverytail endoftherecursion,whenthesubproblemsares osmallthattheyaresolvedoutright;andinthe gluingtogetherofpartialanswers. Theseareheldtogetherandcoordinatedbythea lgorithm's , we'llseehowthistechniqueyieldsa newalgorithmformulti-plyingnumbers, onethatis much moreef cientthanthemethodwealllearnedinelementa ryschool! Gauss(1777 1855)oncenoticedthatalthoughtheproductof twocomplexnumbers(a+bi)(c+di) =ac bd+ (bc+ad)iseemstoinvolvefourreal-numbermul tiplications, it caninfactbedonewithjustthree:ac,bd, and(a+b)(c+d), sincebc+ad=(a+b)(c+d) ac bd:Inourbig-Oway of thinking, reducingthenumberof multiplicationsfromfourtothreeseemswaste dingenuity. Butthismodestimprovementbecomesverysigni 's moveaway , andassumeforconveniencethatnis a powerof2(themoregeneralcaseis hardlyanydifferent).Asa rststeptowardmultiplyingxandy,spliteach of themintotheirleftandrighthalves, which aren=2bitslong:x=xLxR= 2n=2xL+xRy=yLyR= 2n=2yL+ , ifx= 101101102(thesubscript2means binary )thenxL= 10112,xR= 01102,andx= 10112 24+ 01102.

S.Dasgupta,C.H.Papadimitriou,andU.V.Vazirani 59 Figure 2.3 Each problem of size nis divided into asubproblems of size n=b. Size 1 Size n=b2 Size n=b Size n Depth logb n Width alogb n = nlogb a Branching factor a then T(n) = 8 <: O(nd) ifd>log b a O(nd logn) ifd= log b a O(nlogb a) ifd<log b a. This single theorem tells us the running times of most of the divide-and-conquer …

  Conquer, Divide, Divide and conquer