算法分析之分治法学习总结（一）

算法分析之分治法学习总结（一）
一）解决问题的类型：当我们要解决一个输入规模(n)很大的问题时，直接处理往往比较困难或者根本无法
求解，我们希望把输入规模缩小，即分成很多份，分别解决了，并且这些小问题容易合起来从而解决整个问
题。
二）解题关键：
1)如何分:我们往往先把输入分成两个与原来相同的子问题，如果规模还太大，我们
对这些子问题再做上述处理，直到这些子问题容易解决为止.
2)合并子问题:往往分治法的难点在于分完之后怎么合并.合并策略决定了算法的优劣,合并问题根据具体问题而
定,没有固定的方法
3)分治问题往往用到递归算法.
三)几种类型的分治问题:
1)把问题分成字问题后,如果某个子问题解决了则整个问题也就解决了,无须合并.
典型事例:二分检索问题(前提是一组按照关键码排好顺序对象,不妨设按升序排列)
二分检索的解题思路是先看看中间那个数,如果这个数是要查找的,那么ok,问题解决,否则如果比key大,那么
在前一半继续上述过程,否则在后一半继续上述过程,直到找到或者查找失败.
程序代码:(设为int型数)

void BinarySearch(int a[],int low,int high,int key)
{
 
 if(low >= high) return;
 int mid =  (low + hight) / 2;
 if(a[mid] == key) return mid;
 else if(a[mid] > key) 
       return BinarySearch(a[],low,mid,key);
 else if(a[mid] < key) 
       return BinarySearch(a[],mid,low,key);
}

2)把问题分了之后,再经过合并最终解决问题.
典型事例:归并排序问题:
  这个问题就象我们在一个很长的队,现在要按大小个排好,我们把这个队分成两个(如果还是太长,可以再分,
先看分成两个的问题,这样容易看清合并过程),我们把这两队分别排好,然后合成一队,合并的过程很简单,就
是弄一个新的队,从那两个个队的排头分别出列,比一下矮的站在第一个位置,高的在一边等着,等另一个队现
在的排头出列,再比一下,矮的排在第二个位置,高的站在一边,重复上述过程,直到有一个队变空,然后把另一个
队拉过来接在新队的队尾,这就排好了整个队了.
  归并排序,就是把一组待排的关键值可比的东西,我们把他分成两个小组,如果问题规模还不够小,我们继续
分,直到容易解决为止,然后把小的组排好续,然后合并成一组.
算法过程:

void mergeSort(int a[],int low,int high)
{
 if(low >= high)
  return;
 int mid = (low + high) / 2; 
 mergeSort(a,low,mid);
 mergeSort(a,mid+1,high);
 merge(a,low,mid,high);
}
void merge(int a[],int low,int mid,int high)//合并过程
{
 int []b = new int[high-low+1] ;
 int i = low,j=mid+1,k=0;
 while(i <= mid && j <= high)
 {
   if(a[i] < a[j]) 
   {
    b[k++] = a[i];
    i++;
   }
   else
   {
    b[k++] = b[j];
    j++;
   }
 }
 if(i > mid)
  for(int m=j;m<=high;m++)
    b[k++] = a[m];
 else
  for(m=i;m=mid;m++)
   b[k++] = a[m];
 for(m=low,int n=0;m<=high;m++)
 {
   a[m] = b[n++];//排好的元素再拷贝到a中
 }
}