算法设计与分析_第2章_递归与分治2

算法分析(第二章)：递归与分治法一、递归的概念知识再现：等比数列求和公式：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)差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。

算法设计与分析：递归与分治法-实验报告(总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、算法的复杂性取决于：(1)求解问题的规模(N) , (2)具体的输入数据(I),( 3)算法本身的设计(A)，C=F(N,I,A。

3、算法的时间复杂度的上界，下界，同阶，低阶的表示。

4、常用算法的设计技术：分治法、动态规划法、贪心法、回溯法和分支界限法。

5、常用的几种数据结构：线性表、树、图。

第二章递归与分治1、递归算法的思想：将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。

递归的时间复杂性可归结为递归方程：1 11= 1T(n) <aT(n—b) + D(n) n> 1其中，a是子问题的个数，b是递减的步长，~表示递减方式，D(n)是合成子问题的开销。

递归元的递减方式~有两种：1、减法，即n -b，的形式。

2、除法，即n / b，的形式。

2、D(n)为常数c：这时，T(n) = 0(n P)。

D(n)为线形函数cn：r O(n) 当a. < b(NT(n) = < Ofnlog^n) "n = blljI O(I1P)二"A bl吋其中.p = log b a oD(n)为幕函数n x：r O(n x) 当a< D(b)II JT{ii) = O(ni1og b n) 'ia = D(b)ll].O(nr)D(b)lHJI：中，p= log b ao考虑下列递归方程：T(1) = 1⑴ T( n) = 4T(n/2) +n⑵ T(n) = 4T(n/2)+n2⑶ T(n) = 4T(n/2)+n3解：方程中均为a = 4，b = 2，其齐次解为n2。

对⑴，T a > b (D(n) = n) /• T(n) = 0(n);对⑵，•/ a = b2 (D(n) = n2) T(n) = O(n2iog n);对⑶，•/ a < b3(D(n) = n3) - T(n) = 0(n3)；证明一个算法的正确性需要证明两点：1、算法的部分正确性。

算法第⼆章递归与分治策略⼩结第2章递归与分治策略2.1.递归的概念递归算法：直接或间接地调⽤⾃⾝的算法递归函数：⽤函数⾃⾝给出定义的函数递归函数的第⼀句⼀定是if语句作为边界条件，然后就是递归⽅程如：阶乘函数的第⼀句就是if条件语句1int factorial(int n){2if( n ==0)3return1;4return n*factorial(n-1);5 }※※※递归函数中⽐较著名的是Hanoi塔问题Hanoi塔问题。

设a,b,c是3个塔座。

开始时，在塔座a上有⼀叠共n个圆盘，这些圆盘⾃下⽽上，由⼤到⼩地叠在⼀起。

各圆盘从⼩到⼤编号为1,2,…,n,现要求将塔座a上的这⼀叠圆盘移到塔座c上，并仍按同样顺序叠置。

在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较⼤的圆盘压在较⼩的圆盘之上；规则3：在满⾜规则1和2的前提下，可将圆盘移⾄a,b,c中任⼀塔座上。

hanoi塔问题题⽬描述1 #include<iostream>2using namespace std;3void move(char p1,char p2){4 cout<<p1<<"->"<<p2<<endl;5 }67//将a上的n个盘⼦经b移动到c上8void hanoi(int n,char a,char b,char c){9if(n == 0) return;//当a上没有盘⼦的时候，直接返回不需要移动10if(n == 1) move(a,c);//当a上只有⼀个盘⼦的时候，直接将盘⼦从a上移动到c上11if(n>1){12 hanoi(n-1,a,c,b);13 move(a,b);14 hanoi(n-1,c,b,a);15 }16 }1718int main(){19char x,y,z;20 x = 'a';21 y = 'b';22 z = 'c';23 hanoi(4,x,y,z);24return0;25 }Hanoi塔2.2分治法的基本思想分治法的基本思想：将⼀个规模为n的问题分解为k个规模较⼩的⼦问题，这些⼦问题相互独⽴且与原问题相同在使⽤分治法设计算法的时候，最好使⼦问题的规模⼤致相同，即将⼀个问题分为⼤⼩相等的k个⼦问题，⼀般情况k取2.※※※分治法中⽐较著名的是划分整数问题1、整数划分问题将⼀个正整数n表⽰为⼀系列正整数之和，n = n1 + n2 +…+nk其中n1≥n2≥…≥nk≥1, k≥1。