【算法分析与设计】递归与分治策略(一)

简介: 【算法分析与设计】递归与分治策略

一、学习要点

  理解递归的概念。

  掌握设计有效算法的分治策略

  通过下面的范例学习分治策略设计技巧。

  (1)二分搜索技术;

  (2)大整数乘法

  (3)Strassen矩阵乘法;

  (4)棋盘覆盖;

  (5)合并排序和快速排序;

  (6)线性时间选择;

  (7)最接近点对问题;

  (8)循环赛日程表。


二、算法总体思想

  对这k个子问题分别求解。如果子问题的规模仍然不够小,则 再划分为k个子问题如此递归的进行下去直到问题规模足够小,很容易求出其解为止

  将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解

  分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之


三、递归的概念

  直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数

  由分治法 产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生

  分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。


例1 阶乘函数

  阶乘函数可递归地定义为:

  边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果


例2 Fibonacci数列

  无穷数列1,1,2,3,5,8,13,21,34,55,……,称为Fibonacci数列。它可以递归地定义为:

  第n个Fibonacci数可递归地计算如下:

int fibonacci(int n)
   {
       if (n <= 1) return 1;
       return fibonacci(n-1)+fibonacci(n-2);
   }

例3 Ackerman函数

  当一个函数及它的一个变量是由函数自身定义时,称这个函数是双递归函数

  Ackerman函数A(n,m)定义如下:

  前2例中的函数都可以找到相应的非递归方式定义:

  本例中的Ackerman函数却无法找到非递归的定义

  A(n,m)的自变量m的每一个值都定义了一个单变量函数:

  M=0时,A(n,0)=n+2

  M=1时,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2,和A(1,1)=2故A(n,1)=2*n

  M=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2),和A(1,2)=A(A(0,2),1)=A(1,1)=2,故A(n,2)= 2^n 。

  M=3时,类似的可以推出:

  M=4时,A(n,4)的增长速度非常快,以至于没有适当的数学式子来表示这一函数

  定义单变量的Ackerman函数A(n)为,A(n)=A(n,n)。

  定义其拟逆函数α(n)为:α(n)=min{k|A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。

  α(n)在复杂度分析中常遇到。对于通常所见到的正整数n,有α(n)≤4。但在理论上α(n)没有上界,随着n的增加,它以难以想象的慢速度趋向正无穷大。


例4 整数划分问题

  将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。

  正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数

  例如正整数6有如下11种不同的划分:

  6;

  5+1;

  4+2,4+1+1;

  3+3,3+2+1,3+1+1+1;

  2+2+2,2+2+1+1,2+1+1+1+1;

  1+1+1+1+1+1。

  前面的几个例子中,问题本身都具有比较明显的递归关系,因而容易用递归函数直接求解

  在本例中,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。

  (3) q(n,n)=1+q(n,n-1);

  正整数n的划分由n1=n的划分和n1≤n-1的划分组成。

  (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;

  正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤n-1 的划分组成。

  正整数n的划分数p(n)=q(n,n)


例5 Hanoi塔问题

  设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则:

  规则1:每次只能移动1个圆盘;

  规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;

  规则3:在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。

void hanoi(int n, int a, int b, int c)
   {
       if (n > 0)
       {
          hanoi(n-1, a, c, b);
          move(a,b);
          hanoi(n-1, c, b, a);
       }
   }

递归小结

  优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。

  缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多

  解决方法:在递归算法中消除递归调用,使其转化为非递归算法

  1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强,但本质上还是递归,只不过人工做了本来由编译器做的事情,优化效果不明显。

  2、用递推来实现递归函数

  3、通过变换能将一些递归转化为尾递归,从而迭代求出结果。

  后两种方法在时空复杂度上均有较大改善,但其适用范围有限。


四、分治法

1、分治法的适用条件

  分治法所能解决的问题一般具有以下几个特征:

  该问题的规模缩小到一定的程度就可以容易地解决

  该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解;

  该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

  这条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可用分治法,但一般用动态规划较好。

divide-and-conquer(P)
  {
    if ( | P | <= n0) adhoc(P);   //解决小规模的问题
    divide P into smaller subinstances P1,P2,...,Pk;//分解问题
    for (i=1,i<=k,i++)
      yi=divide-and-conquer(Pi);  //递归的解各子问题
    return merge(y1,...,yk);  //将各子问题的解合并为原问题的解
  }

  人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。

  一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:

  通过迭代法求得方程的解:

  注意:递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的,从而当mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1)。


目录
打赏
0
0
0
0
7
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
124 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
266 11
架构学习:7种负载均衡算法策略
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
73 16
机器学习算法的优化与改进:提升模型性能的策略与方法
机器学习算法的优化与改进:提升模型性能的策略与方法
289 13
机器学习算法的优化与改进:提升模型性能的策略与方法
【算法】——快排,分治算法合集
本文主要介绍排序中的快排思想的应用,做到一法通万法的效果
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
56 6
通过matlab分别对比PSO,反向学习PSO,多策略改进反向学习PSO三种优化算法
本项目使用MATLAB2022A版本,对比分析了PSO、反向学习PSO及多策略改进反向学习PSO三种优化算法的性能,主要通过优化收敛曲线进行直观展示。核心代码实现了标准PSO算法流程,加入反向学习机制及多种改进策略,以提升算法跳出局部最优的能力,增强全局搜索效率。
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等