Transcription of Divide-and-conquer algorithms - EECS at UC Berkeley
{{id}} {{{paragraph}}}
Example: confidence
Divide-and-conquer algorithms - EECS at UC Berkeley
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).
Divide-and-conquer algorithms The divide-and-conquer strategy solves a problem by: 1. Breaking it into subproblems that are themselves smaller instances of the same type of problem 2. Recursively solving these subproblems 3. Appropriately combining their answers The real work is done piecemeal, in three different places: in the partitioning of ...
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: