分治[2019.5.25]

　　1、为最近对问题的一维版本设计一个直接基于分治技术的算法,并确定它的时间复杂度。假设输入的点是以升序保存在数组A中。（最近点对问题定义：已知上m个点的集合，找出对接近的一对点。）

　　思路：通过分治和递归将问题自顶向下分为层层的子问题，然后每层中子问题自底向上min向上比较。

　　输入：保存升序点序列的数组A

int Close(int A[a...b]){
    if(a==b)return error;
    else if(b-a==1)return A[b]-A[a];
    else{
          int c = int((a+b)/2);   //多个数时，分治&递归求每个子问题，然后min
          return min{Close(A[a…c]), Close(A[c...b]), A[c+1]-A[c]}; 
    }
}

　　输出：最近的一对数的距离

　　时间复杂度：θ(n)

　　2、设计一个分治算法来计算二叉树的层数.(空树返回0,单顶点树返回1),并确定它的时间复杂度.

　　思路：水题，对于二叉树T，若为空树，则高度为0；否则，分别求左子树和右子树高度，递归即可。

　　输入：二叉树T

int height(Tree T){
if T=NULL
    return 0；
else return max{height(left_T),height(right_T)}+1;
}

　　输出：二叉树的层数

　　时间复杂度：θ(n)