算法基础Spring 2012, USTCUniversityofScience andTechnology ofhina
University of Science and Technology of China Spring 2012 ，USTC 算法基础
第四讲递归和分治策略口通过例子理解递归的概念：口掌握设计有效算法的分治策略：口通过几个范例学习分治策略设计技巧MergesortMultiplication oftwo numbersMultiplication of two matricesFinding Minimum and MaximumMajorityproblem（多数问题）国窗niversity of cience and Technology of China
University of Science and Technology of China 第四讲 递归和分治策略 2 通过例子理解递归的概念； 掌握设计有效算法的分治策略； 通过几个范例学习分治策略设计技巧； ✓ Merge sort ✓ Multiplication of two numbers ✓ Multiplication of two matrices ✓ Finding Minimum and Maximum ✓ Majority problem (多数问题)
算法总体思想对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。T(n)T(n/2)T(n/2)T(n/2)T(n/2)3niversity of Science andTechnology of China
3 University of Science and Technology of China 算法总体思想 ⚫ 将要求解的较大规模的问题分割成k个更小规模的子问 题。 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = ◼ 对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止
算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解T(n)n/2n/2n/2n/2TnVn4/204Vn0/4Yn4n4)YnaMnA20AznaVnniversity of Science and Technology of China
4 University of Science and Technology of China 算法总体思想 ◼ 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4)
算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。分治法的设计思想是，将一个难以直接解决的大问题分割成一些规模较小的相同问题，以便各个击破，分而治之。niversity of clence andlechnology of Chna
5 University of Science and Technology of China 算法总体思想 ◼ 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。 n T(n) = n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) n/2 T(n/4)T(n/4)T(n/4)T(n/4) 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之