下载文档原格式
递归与分治算法心得
递归与分治算法都是常用的算法思想，可以很好地解决复杂问题。
递归算法是通过将问题分解为相同或相似的子问题来解决整个问题，然后再逐步合并回原问题的过程。
递归算法通常需要明确边界条件，以确保递归能够正确地停止。
分治算法是将问题分解成若干个相同或相似的子问题，递归地解决这些子问题，然后合并这些子问题的解来解决原始问题。
通常，分治算法可以高效地解决问题，但需要注意分解问题的方式和合并子问题的解的过程。
在实际应用中，递归和分治算法可以相互结合，以解决更加复杂的问题。
例如，可以使用分治算法来将问题分解成多个子问题，然后使用递归算法来解决这些子问题。
此外，还可以在递归算法中使用分治算法来对子问题进行分解和合并。
总而言之，递归与分治算法都是非常有用的算法思想，可以在许多领域中得到应用。
但是，在实际使用时，需要仔细考虑问题的性质和算法的复杂度，以确保算法的正确性和效率。
- 1 -。
递归与分治算法心得
递归与分治算法是算法设计中常见的两种方法，它们在解决问题时都采用了“分而治之”的思想，将问题分解成更小的子问题，然后通过递归调用或者合并子问题的解来得到原问题的解。
通过我的学习和实践，我深刻认识到了递归与分治算法的重要性和优势。
首先，递归算法可以使问题的描述更加简单明了。
通过将问题转化为自身的子问题，我们可以建立起更为简洁优美的数学模型。
其次，递归算法可以使问题的解决过程更加自然。
在递归过程中，我们可以利用已知的子问题解决同类问题，实现代码的复用和模块化。
此外，递归算法还可以解决一些重要的数学问题，如斐波那契数列和二分查找等。
分治算法则更加注重问题的分解和合并。
它将问题划分成若干个规模相同或相近的子问题，然后将子问题的解合并起来得到原问题的解。
这种方法在解决某些复杂问题时具有很大的优势。
例如，在排序算法中，归并排序采用了分治算法的思想，将待排序的序列分成两个长度相等的子序列，然后递归地对子序列排序，最后将子序列合并成有序序列。
这种算法具有较高的稳定性和灵活性，常常被应用于海量数据的排序任务中。
总之，递归与分治算法是算法设计中不可或缺的两种方法。
在解决问题时，我们应该根据具体情况选择合适的算法，并在实践中不断探索、总结和优化。
只有这样，我们才能更好地应对日益复杂多变的计算机科学挑战。
递归和分治法摘要：1.递归和分治法的定义2.递归和分治法的区别3.递归和分治法的应用实例4.递归和分治法的优缺点正文：递归和分治法是计算机科学中常用的两种算法设计技巧。
它们在解决问题时都采用了将问题分解成更小子问题的思路，但在具体实现上却有所不同。
下面，我们来详细了解一下递归和分治法。
1.递归和分治法的定义递归法是指在算法中调用自身来解决问题的方法。
递归函数在执行过程中，会将原问题分解成规模更小的相似子问题，然后通过调用自身的方式，解决这些子问题，最后将子问题的解合并，得到原问题的解。
分治法是指将一个大问题分解成若干个规模较小的相似子问题，然后分别解决这些子问题，最后将子问题的解合并，得到原问题的解。
分治法在解决问题时，通常需要设计一个主函数（master function）和一个子函数（subfunction）。
主函数负责将问题分解，子函数负责解决子问题。
2.递归和分治法的区别递归法和分治法在解决问题时都采用了将问题分解成更小子问题的思路，但它们在实现上存在以下区别：（1）函数调用方式不同：递归法是通过调用自身来解决问题，而分治法是通过调用不同的子函数来解决问题。
（2）递归法必须有递归出口，即必须有一个基线条件，而分治法不一定需要。
3.递归和分治法的应用实例递归法应用广泛，例如斐波那契数列、汉诺塔问题、八皇后问题等。
分治法也有很多实际应用，例如快速排序、归并排序、大整数乘法等。
4.递归和分治法的优缺点递归法的优点是代码简单易懂，但缺点是容易产生大量的重复计算，导致时间复杂度较高。
分治法的优点是时间复杂度较低，但缺点是代码实现相对复杂，需要设计主函数和子函数。
总之，递归和分治法都是解决问题的有效方法，具体应用需要根据问题的特点来选择。
算法设计与分析：递归与分治法-实验报告(总8页)实验目的：掌握递归与分治法的基本思想和应用，学会设计和实现递归算法和分治算法，能够分析和评价算法的时间复杂度和空间复杂度。
实验内容：1.递归算法的设计与实现3.算法的时间复杂度和空间复杂度分析实验步骤：1）递归定义：一个函数或过程，在其定义或实现中，直接或间接地调用自身的方法，被成为递归。
递归算法是一种控制结构，它包含了解决问题的基础情境，也包含了递归处理的情境。
2）递归特点：递归算法具有以下特点：①依赖于递归问题的部分解被划分为若干较小的部分。
②问题的规模可以通过递推式递减，最终递归终止。
③当问题的规模足够小时，可以直接求解。
3）递归实现步骤：①确定函数的定义②确定递归终止条件③确定递归调用的过程4）经典实例：斐波那契数列递推式：f(n) = f(n-1) + f(n-2)int fib(int n) {if (n <= 0)return 0;else}5）优化递归算法：避免重复计算例如，上述斐波那契数列的递归算法会重复计算一些中间结果，影响效率。
可以使用动态规划技术，将算法改为非递归形式。
int f1 = 0, f2 = 1;for (int i = 2; i <= n; i++) {f1 = f2;使用循环避免递归，重复计算可以大大减少，提高效率。
1）分治算法的定义：将原问题分解成若干个规模较小且类似的子问题，递归求解子问题，然后合并各子问题得到原问题的解。
2）分治算法流程：②将问题分解成若干个规模较小的子问题。
③递归地解决各子问题。
④将各子问题的解合并成原问题的解。
3）分治算法实例：归并排序归并排序是一种基于分治思想的经典排序算法。
排序流程：②分别对各子数组递归进行归并排序。
③将已经排序好的各子数组合并成最终的排序结果。
实现源代码：void mergeSort(int* arr, int left, int right) {if (left >= right)while (i <= mid && j <= right)temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];temp[k++] = arr[i++];1) 时间复杂度的概念：指完成算法所需的计算次数或操作次数。
算法分析(第二章)：递归与分治法一、递归的概念知识再现：等比数列求和公式：1、定义：直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2、与分治法的关系：由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。
3、递推方程：(1)定义：设序列01,....na a a简记为{na}，把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。
(2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。
4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点：优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
二、递归算法改进：1、迭代法：(1)不断用递推方程的右部替代左部(2)每一次替换，随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例：-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−（1）=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−（1）2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代：(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解（关于k 的函数）转换成关于n 的函数4、举例：---------------二分归并排序---------------()2(/2)1W n W n n W =+−（1）=0（1）换元：假设2kn =，递推方程如下()2(/2)1W n W n n W =+−（1）=0 → 1(2)2(2)21k k k W W W−=+−（0）=0（2）迭代求解：12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+（3）解的正确性—归纳验证： 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−（1）=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法：数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程，则（）---------------快速排序--------------------->>>平均工作量：假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简，然后迭代(1)差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。
算法分析(第二章)：递归与分治法一、递归的概念知识再现：等比数列求和公式：1、定义：直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2、与分治法的关系：由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。
3、递推方程：(1)定义：设序列01,....na a a简记为{na}，把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。
(2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。
4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点：优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
二、递归算法改进：1、迭代法：(1)不断用递推方程的右部替代左部(2)每一次替换，随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例：-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−（1）=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−（1）2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代：(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解（关于k 的函数）转换成关于n 的函数4、举例：---------------二分归并排序---------------()2(/2)1W n W n n W =+−（1）=0（1）换元：假设2kn =，递推方程如下()2(/2)1W n W n n W =+−（1）=0 → 1(2)2(2)21k k k W W W−=+−（0）=0（2）迭代求解：12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+（3）解的正确性—归纳验证： 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−（1）=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法：数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程，则（）---------------快速排序--------------------->>>平均工作量：假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简，然后迭代(1)差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。
111212212()()()()2()(1)(1)2()(1)n i n i n i T n T i O n n nT n T i cn n T n T i c n −=−=−==+=+−−=+−∑∑∑ 122211()(1)(1)2()(2()(1))2(1)1()(1)(1)1()(1)111n n i i nT n n T n T i cn T i c n T n c nnT n n T n c nT n T n c n n n −−==−−−=+−+−=−+=+−+−=+++∑∑(2)迭代求解：()(1)111111(1)1(...)1321111(...)13(log )()(log )T n T n c n n n T c n n c n n n T n n n θθ−=+++=+++++=++++==三、递归树1、概念(1)递归树是迭代计算的模型(2)递归树的生成过程与迭代过程一致(3)递归树上所有项恰好是迭代之后产生和式中的项 (4)对递归树上的项求和就是迭代后方程的解 2、迭代在递归树中的表示111(()...()()...(),....()...()t t t W m W m W m f m g m m m mW m W m =+++++<++）其中称为函数项注意：每个叶结点是一个函数项3、二层子树的例子二分归并排序：(2(/2)1W n W n n =+−） →4、递归树的生成规则 ·初始：递归树只有根节点，其值为W(m) ·不断继续下述过程：将函数项叶节点的迭代式W(m)表示成二层子树 用该子树替换该叶节点·继续递归树的生成，直到树中无函数项（只有初值）为止 5、递归树生成实例(2(/2)1W n W n n =+−）>>>对递归树上的量求和：11(2(/2)1,2,(1)0()12...2(2)log 1k k k W n W n n n W W n n n n kn n n n −−=+−===−+−++−=−=−+）四、Master 定理（主定理）--------------它提供了一种通过渐近符号表示递推关系式的方法。
1、应用背景：T （n ）=aT(n/b)+f(n)a ：规约后的子问题个数 n/b ：规约后子问题的规模f(n):归约过程及组合子问题的解的工作量T 二分检索：（n ）=T(n/2）+1二分归并排序：T(n)=2T(n/2)+n-12、定理：1,1a b T ≥>定理：设为常数，f(n)为函数，T(n)为非负整数，且（n ）=aT(n/b)+f(n)，则log log log log log +1.logn .c<1n (/)(),n =a b abab abab af n b cf n T εεεθθθεθ−∃Ω∃≤若f(n)=O(n ),>0,那么T(n)=(n )2.若f(n)=(n )，那么T(n)=(n)3若f(n)=(n ),>0,且对于某个常数和充分大的有那么（）（f(n)）3、应用：9933log log 12a −例1：求解递推方程：T(n)=9T(n/3)+n 解 上述递推方程中的=9,b=3,f(n)=n n=n ,f(n)=O(n)2=1 T(n)=(n )εθ相当于主定理的第一种情况，其中根据定理得到13/2log 0a 例2：求解递推方程：T(n)=T(2n/3)+1解 上述递推方程中的=1,b=3/2,f(n)=1n=n =1,T(n)=(logn)θ相当于主定理的第二种情况，根据定理得到12log n =W(n/2)+1,W(1)=1a=1,b=2,n 1,()1n =logn W f n W θ==递归算法分析二分检索：（）属于主定理第二种情况，（）（）22log n =2W(n/2)+n-1,W(1)=0a=2,b=2,n n,()n-1n =nlogn W f n W θ==二分归并排序：（）属于主定理第二种情况，（）（）不能使用主定理的例子：22log 1n =0nlogn=()T n εε+>Ω求解（）2T(n/2)+nlogn a=2,b=2,n=n,f(n)=nlogn不存在使下式成立c<1af(n/b)cf(n)≤≤不存在使对所有充分大的n 成立2(n/2)log(n/2)=n(logn-1)cnlogn五、分治法1、基本思想：将一个规模为n 的问题分解为k 个规模较小的子问题，这些子问题互相独立且与原问题相同。
递归地求解这些子问题，然后将各子问题的解合并得到原问题的解。
2、设计过程：–Divide ：整个问题划分为多个子问题–Conquer ：求解各子问题(递归调用正设计的算法) –Combine ：合并子问题的解, 形成原始问题的解 注意：(1)子问题与原问题性质完全一样 (2)子问题之间可彼此独立的求解 (3)递归停止时子问题可直接求解 3、算法分析:设输入大小为n ，T(n)为时间复杂性 – Divide 阶段的时间复杂性 • 划分问题为a 个子问题 • 每个子问题大小为n/b • 划分时间可直接得到=D(n) – Conquer 阶段的时间复杂性 • 递归调用• 求解时间= a T(n/b)– Combine 阶段的时间复杂性 • 时间可以直接得到=C(n) T(n)=θ(1) if n<cT(n)=a T(n/b) + D(n)+C(n) otherwise 4、分治算法的特点：(1)将原问题归约为规模小的子问题(子问题与原问题具有相同的性质)(2)子问题规模足够小时可直接求解 (3)算法可以递归也可以迭代实现 (4)算法的分析方法：递推方程 5、分治法的一般描述分治算法 divide-and-conquer(P)1. if | P | <= c then S(P) //2.divide P into P1, P2, ..., Pk //3. for i←1 to k4. yi=divide-and-conquer(Pi) //5. 6、设计要点(1)原问题可以划分或者归约为规模较小的子问题 注意：子问题与原问题具有相同的性质子问题的求解彼此独立划分时子问题的规模尽可能均衡 (2)子问题的规模足够小时可直接求解 (3)子问题的解综合得到原问题的解 (4)算法的实现：递归或迭代 7、分治算法时间分析(1)时间复杂度函数的递推方程：12()(||)(||)...(||)()()k W n W P W P W P f n W c C=++++= >>>P1,P2,…P k 为划分后产生的子问题>>>f(n)为划分子问题以及将子问题综合得到原问题解的总工作量 >>>规模为c 的最小子问题的工作量为C(2)两类常见的递推方程:11()()()2()()()ki i T n a T n i f n nT n aT f n b==−+=+∑方程：方程：求解方法：方程1：迭代法，差消化简，递归树方程2：迭代法，换元法，递归树，主定理2()()()nT n aT f n b =+方程：log log ()() a 1()O(logn) a=1()() a<b ()O(nlogn) a=bO() a>b ab a bf n O n T n f n cnO n T n n ⎧≠⎪=⎨⎪⎩=⎧⎪=⎨⎪⎩为常数六、分治法的应用1、二分搜索技术问题描述：给定已按升序排好序的n 个元素a[1:n]，现要在这n 个元素中找出一特定元素x 分析：✓ 该问题分解出的各个子问题是相互独立的，可以分解为若干个规模较小的相同问题；✓ 该问题的规模缩小到一定的程度就可以容易地解决； ✓ 分解出的子问题的解可以合并为原问题的解； 算法设计思想：⚫ 通过x 与中位数T(m)比较，将原问题归结为规模减半的子问题，如果x 小于中位数，则子问题由小于T(m)的数构成，否则由大于T(m)的数构成。
