第四讲递归和分治策略 口通过例子理解递归的概念; 口掌握设计有效算法的分治策略; 口通过几个范例学习分治策略设计技巧; Merge sort Binary search Powering a number Fibonacci number Multiplication of two matrices VLSI layout Multiplication of two numbers Finding Minimum and Maximum Majority problen(多数问题)循环赛日程表
第四讲 递归和分治策略 2 通过例子理解递归的概念； 掌握设计有效算法的分治策略； 通过几个范例学习分治策略设计技巧； Merge sort Binary Search Powering a number Fibonacci number Multiplication of two matrices VLSI layout Multiplication of two numbers Finding Minimum and Maximum Majority problem (多数问题) 循环赛日程表
算法总体思想 对这k个子问题分别求解。如果子问题的规模仍然不够 ●小,则再划分为k个子问题,如此递归的进行下去,直 到问题规模足够小,很容易求出其解为止。 n T(n) T(n/2) T(n/2) T(n/2) T(n/2)
3 算法总体思想 ⚫ 将要求解的较大规模的问题分割成k个更小规模的子问 题。 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = ◼ 对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止
算法总体思想 ■将求出的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 T(n)
4 算法总体思想 ◼ 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。 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)
算法总体思想 ■将求出的小规模的问题的解合并为一个更大规模的问 题的解,自底向上逐步求出原来问题的解。 分治法的设计思想是,将一个难以直接解决的大问题 分割成一些规模较小的相同问题,以便各个击破, 分而治之
5 算法总体思想 ◼ 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。 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) 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之
递归的概念 直接或间接地调用自身的算法称为递归算法。用函数 自身给出定义的函数称为递归函数。 ●由分治法产生的子问题往往是原问题的较小模式,这 就为使用递归技术提供了方便。在这种情况下,反复 应用分治手段,可以使子问题与原问题类型一致而其 规模却不断缩小,最终使子问题缩小到很容易直接求 出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟,经常同时应用在算法设 计之中,并由此产生许多高效算法。 下面来看几个实例
6 递归的概念 ⚫ 直接或间接地调用自身的算法称为递归算法。用函数 自身给出定义的函数称为递归函数。 ⚫ 由分治法产生的子问题往往是原问题的较小模式，这 就为使用递归技术提供了方便。在这种情况下，反复 应用分治手段，可以使子问题与原问题类型一致而其 规模却不断缩小，最终使子问题缩小到很容易直接求 出其解。这自然导致递归过程的产生。 ⚫ 分治与递归像一对孪生兄弟，经常同时应用在算法设 计之中，并由此产生许多高效算法。 下面来看几个实例