当前位置:   article > 正文

算法练习:分治法_分治法进阶练习

分治法进阶练习

分治法

  • 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
  • 精髓
    分–将问题分解为规模更小的子问题;
    治–将这些规模更小的子问题逐个击破;
    合–将已解决的子问题合并,最终得出“母”问题的解;
  • 可解决问题的特征
  1. 该问题的规模缩小到一定的程度就可以容易地解决
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解;
  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。
  • 生活实例
    在一堆硬币中有一个是假币,重量较真币轻,若两两相比费时费力。采用分治法,将硬币分成两堆相比,将轻的那一堆再分成两堆相比……
  • 经典应用
    1. 折半搜索
    折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是:(这里假设数组元素呈升序排列)将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止;如 果x<a[n/2],则我们只要在数组a的左半部继续搜索x;如果x>a[n/2],则我们只要在数组a的右 半部继续搜索x。
public static int binarysearch(int[] num,int x){
   
		int L=0;
		int R=num.length-1;
		while(L<=R) {
   
			int mid=L+(R-L)/2;//不要用(L+R)/2,有可能溢出int
			if(x==num[mid]) return mid;	
			else if(x>num[mid]) L=mid+1;
			else R=mid-1;
		}
		return -1;
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

2. 归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列。步骤如下:
1)申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
2)设定两个指针,最初位置分别为两个已经排序序列的起始位置;
3)比较两个指针所指向的元素,选择较小的元素放入到合并空间,并移动指针到下一位置;
4) 重复步骤 3 直到某一指针达到序列尾;
5)将另一序列剩下的所有元素直接复制到合并序列尾。
图片来源https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg

public static void GB(int[] arr,int start,int end,int[] help) {
   
		if(start<end) {
   
			int mid=start+(end-start)/2;
			GB(arr,start,mid,help);
			GB(arr,mid+1,end,help);
			HB(arr,start,mid,end,help);
		}
		
	}
	public static void HB(int[] arr, int start
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/716400
推荐阅读
相关标签
  

闽ICP备14008679号