Transcription of Divide-and-conquer algorithms
{{id}} {{{paragraph}}}
Example: confidence
Divide-and-conquer algorithms
Chapter2 divide -and-conqueralgorithmsThedivide-an d-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).
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 …
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: