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

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

2、二分搜索技术

  给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。

  分析:

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

  该问题可以分解为若干个规模较小的相同问题;

  分解出的子问题的解可以合并为原问题的解

  分解出的各个子问题是相互独立的

  分析:很显然此问题分解出的子问题相互独立,即在a[i]的前面或后面查找x是独立的子问题,因此满足分治法的第四个适用条件。

  据此容易设计出二分搜索算法

template<class Type> 
int BinarySearch(Type a[], const Type& x, int l, int r)
{
     while (r >= l){ 
        int m = (l+r)/2;
        if (x == a[m]) return m;
        if (x < a[m]) r = m-1; else l = m+1;
        }
    return -1;
} 

  算法复杂度分析:

  每执行一次算法的while循环, 待搜索数组的大小减少一半。因此,在最坏情况下,while循环被执行了O(logn) 次循环体内运算需要O(1) 时间,因此整个算法在最坏情况下的计算时间复杂性为O(logn)


3、大整数的乘法

  请设计一个有效的算法,可以进行两个n位大整数的乘法运算。

  小学的方法:O(n2) ×效率太低

  分治法:

  XY = ac 2n + ((a-b)(d-c)+ac+bd) 2n/2 + bd

  XY = ac 2n + ((a+b)(c+d)-ac-bd) 2n/2 + bd

  细节问题:两个XY的复杂度都是O(nlog3),但考虑到a+b,c+d可能得到m+1位的结果,使问题的规模变大,故不选择第2种方案。

  小学的方法:O(n2)   ×效率太低

  分治法: O(n1.59)   √较大的改进


  如果将大整数分成更多段,用更复杂的方式把它们组合起来,将有可能得到更优的算法

  最终的,这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法。


4、Strassen矩阵乘法

  传统方法:O(n3)

  若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C[i][j],需要做n次乘法和n-1次加法。因此,算出矩阵C的 个元素所需的计算时间为O(n3)

  使用与上例类似的技术,将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为:

  由此可得:

  传统方法:O(n3)

  分治法:

  为了降低时间复杂度,必须减少乘法的次数。

  传统方法:O(n3)

  分治法: O(n2.81)

  更快的方法??

  Hopcroft和Kerr已经证明(1971),计算2个2×2矩阵的乘积,7次乘法是必要的。因此,要想进一步改进矩阵乘法的时间复杂性,就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究3×3或5×5矩阵的更好算法。

  在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)

  是否能找到O(n2)的算法?


5、棋盘覆盖

  在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖

  当k>0时,将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示

  特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如 (b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为棋盘1×1。

void chessBoard(int tr, int tc, int dr, int dc, int size){
      if (size == 1) return;
      int t = tile++,  // L型骨牌号
        s = size/2;  // 分割棋盘
      // 覆盖左上角子棋盘
      if (dr < tr + s && dc < tc + s)
         // 特殊方格在此棋盘中
         chessBoard(tr, tc, dr, dc, s);
      else {// 此棋盘中无特殊方格
         // 用 t 号L型骨牌覆盖右下角
         board[tr + s - 1][tc + s - 1] = t;
         // 覆盖其余方格
         chessBoard(tr, tc, tr+s-1, tc+s-1, s);}
      // 覆盖右上角子棋盘
      if (dr < tr + s && dc >= tc + s)
         // 特殊方格在此棋盘中
         chessBoard(tr, tc+s, dr, dc, s);
      else {// 此棋盘中无特殊方格
         // 用 t 号L型骨牌覆盖左下角
            board[tr + s - 1][tc + s] = t;
         // 覆盖其余方格
         chessBoard(tr, tc+s, tr+s-1, tc+s, s);}
        // 覆盖左下角子棋盘
      if (dr >= tr + s && dc < tc + s)
         // 特殊方格在此棋盘中
         chessBoard(tr+s, tc, dr, dc, s);
      else {// 用 t 号L型骨牌覆盖右上角
         board[tr + s][tc + s - 1] = t;
         // 覆盖其余方格
         chessBoard(tr+s, tc, tr+s, tc+s-1, s);}
      // 覆盖右下角子棋盘
      if (dr >= tr + s && dc >= tc + s)
         // 特殊方格在此棋盘中
         chessBoard(tr+s, tc+s, dr, dc, s);
      else {// 用 t 号L型骨牌覆盖左上角
         board[tr + s][tc + s] = t;
         // 覆盖其余方格
         chessBoard(tr+s, tc+s, tr+s, tc+s, s);}
   }   

  T(n)=O(4k) 渐进意义下的最优算法


6、合并排序

  基本思想:将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合

  T(n)=O(nlogn) 渐进意义下的最优算法

void MergeSort(Type a[], int left, int right)
   {
      if (left<right) {//至少有2个元素
      int i=(left+right)/2;  //取中点
      mergeSort(a, left, i);
      mergeSort(a, i+1, right);
      merge(a, b, left, i, right);  //合并到数组b
      copy(a, b, left, right);    //复制回数组a
      }
   }

  算法mergeSort的递归过程可以消去。

  最坏时间复杂度:O(nlogn)

  平均时间复杂度:O(nlogn)

  辅助空间:O(n)

目录
打赏
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提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。

热门文章

最新文章