分治递归算法总结

分治策略是大问题分为小问题在递归向下分。个个小问题互不依赖，同时独立的求解，自底向上合并出原问题的解，还有简要介绍了其余具体问题的相关策略和算法，

分治递归

• 策略和方法
  • 分治策略
    • 大问题分为小问题，再递归向下分（问题类型一致）
    • 各个小问题互不依赖，同时独立地求解
    • 自底向上合并出原问题的解
  • 递归策略
    • 再分治向下缩减过程中出现
    • 两个要素
      • 边界条件
      • 递归方程
    • 经典问题
      • 排列问题
        • 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素
        • 当n>1时，perm(R)由 (r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)
      • 整数划分问题
        • 增加一个自变量：将最大加数n1不大于m的划分个数记作q(n, m)，e.g. q(6, 3)
        • (1) q(n, 1)=1, n1; e.g. 6=1+1+1+1+1+1 //当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 n=1+1+…+1 (2) q(n, m)=q(n,n), mn; e.g. q(6, 7)=q(6, 6) //最大加数n1=m实际上不能大于n, 因此，q(1,m)=1 (3) !!!p(n)=q(n, n)=1 + q(n, n-1) //问题规模中第2变量减小 正整数n的划分由n1=n的划分和n1≤n-1的划分组成 e.g. q(6, 6) = 1 + q(6, 5) (4) q(n, m)=q(n, m-1)+q(n-m, m), n>m>1; e.g. n=6, m=4, q(6, 4) = q(6,3) + q(2, 4) = q(6,3) + q(2, 2)
      • 汉诺塔问题
        • hanoi(n-1, a, c, b); /*将A上的n-1个盘子，借助B，移到C move(a,b); /*将A上剩余的最大/最底层盘子直接移到B hanoi(n-1, c, b, a); /*将C上的n-1个盘子， 借助A，移到B上
    • 改进
      • 用户定义栈
      • 递推来实现递归
      • 转化为尾递归
  • 设计方法
    • 适用问题
      • 最优子结构性质---规模较小的相同问题
      • 利用分解出的子问题的解可以合并出该问题的解，各个子问题之间没有一定依赖关系
        • 如果不行-----》动态规划或贪心算法
    • 设计原理和求解步骤
      • if 规模小---》解决
      • 如果规模大---》分解
        • 注意balance
      • 递归解决子问题
      • 合并得解
    • 复杂度
      • 将规模为n的问题分成k个规模为n/m的子问题
        • 共有logmn-1 层
        • 第j层问题规模 n/mj
        • 第j层问题数量是k的j次方
      • • 串行求解的代价
        • 各层分解和合并代价累加
• 具体问题
  • 二分搜索
    • 减治没有递归
      • int BinarySearch(Type a[], const Type& x, int l, int r) { while (r >= l){ int mid = (l+r)/2; if (x == a[mid]) return mid; if (x < a[mid]) r = mid-1; else l = mid+1; } return -1; }
    • O(logn)
  • 排序
    • 合并排序
      • 简单合并排序
        • 步骤
          • 1. 将数组a分成左右两个部分
            • if (left<right) { //*至少有2个元素 int i=(left+right)/2; //*取中点
          • 2. 将左右两个部分分别调用合并排序
            • mergeSort(a, left, i); //*左子问题求解 mergeSort(a, i+1, right); //*右子问题求解
          • 3. 将左右结果merge合并成b
            • merge(a, b, left, i, right); //合并、copy到数组b, 关键 !
              • 0. 设立三个指针，一个是目标数组的指针，另外两个分别是左右两个顺序数组的指针
                • int i=l, //左子段的搜索比较指针的起点 j=m+1, //右子段的搜索比较指针的起点 k=l;
              • 1. 同时从左向右扫描左边和右边的数组
                • while (( i<=m) && (j<=r)
              • 2. 如果当下左指针更大，则将左指针的值赋予给目标数组指针，并且二者向前移动。else对右边指针同理
                • if (c[i] <=c[j]) d[k++]=c[i++]; else d[k++]=c[j++];
              • 3. 步骤2中每次移动之后，紧跟着检查是左右指针是否超出界限，如果超，则另一部分没超的数组剩下的部分全部放在目标数组最后。
                • f (i>m) for (int q=j; q<=r; q++) d[k++]=c[q]; else for (int q=i; q<=m; q++) d[k++]=c[q];
          • 4. 将数组b复制回数组a
        • 复杂度
          • 最坏时间复杂度 O(nlogn) 平均时间复杂度 O(nlogn) 辅助空间：O(n)
      • 改进--非递归合并排序
        • 省略自上而下的分解过程，将a[]中相邻元素两两配对，作为最底层子问题，由下而上使用merge过程，进行排序
        • 步骤
          • 0. 创建中转数组b
          • 1. 设置合并的长度的初始值 s = 1
          • 2. 当合并的长度值小于n 的时候，一直进行一下合并步骤
          • 3. 一次循环里两次合并，解决了b复制回去的问题
            • MergePass(a, b, s, n);
              • 0. 设置一个要合并的两端数组的起始位置指针，初始值是i=0
              • 1. 当没有到头的阶段，大部分的数组执行归并 (i<=n-2*s)
                • Merge(x, y, i, i+s-1, i+2*s-1);
                • i=i+2*s;
              • 2. 循环跳出，已经到头
                • 如果最后部分长度小于s，直接复制到目标数组最后
                  • for (int j=i; j<n-1; j++) y[j]=x[j];
                • 如果在s和2s之间 (i+s<=n),把mergr的目标点改成尾部，还是要merge
                  • Merge(x, y, i, i+s-1, n-1);
            • s+=s;
            • MergePass(b, a, s, n); //合并到数组a
            • s+=s;
    • 快速排序
      • 步骤
        • 0. 当至少有两个元素的时候
        • 1. 挑选a[q]，划分a[]为两个左右部分，右边永远比左边的大
          • Partition(a,p,r)
            • 0.挑选开头元素作为基准元素x
            • 1. 设立两个指针，从左向右i和从右向左j
            • 2. 当i<j的时候持续进行交换
              • i从左向右搜到比基准x大的位置,j从右向左搜到比x小的位置
                • while (a[++i] <x && i<r); while (a[- -j] >x);
              • 交换这两个位置的元素
                • Swap(a[i], a[j]);
            • 3. 将j位置的元素和基准元素互换
              • a[p] = a[j]; a[j] = x;
        • 对左半段递归排序
          • QuickSort (a,p,q-1);
        • 对右半段递归排序
          • QuickSort (a,q+1,r);
      • 改进
        • 避免对已排序的数组划分
          • 非递减，则直接返回
          • 非递增，则倒序后返回
        • 随机选择划分的基准元素
          • 选择之后将其交换到第一个位置，这样其他步骤就保持不变
      • 复杂度
        • 最坏时间复杂度：O(n2)
        • 平均时间复杂度：Θ(nlgn)
        • 最好时间复杂度：(nlogn)
        • 辅助空间：O(n)或O(logn)
    • 基于比较的排序算法的最坏时间复杂度，渐进下界是 Ω(nlogn)
  • 乘法
    • 大整数乘法
      • 逐位相乘再相加——n2次乘法，O(n)次加法 效率太低
        • 主要要减少乘法次数
      • 方法一，没有改进——XY = ac 2n + (bc+ad) 2n/2 + bd
        • m=2,k=4
      • 方法二——用2次减法和一次加法换一次乘法——ac 2n + ( (a-b)(d-c) + ac + bd) 2n/2 + bd
        • m=2,k=3
    • Strassen矩阵乘法
      • 对于2*2的矩阵乘法，转化为7次乘法
  • 线性时间选择
    • 给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素
    • 步骤
      • 1. 从数组a中选择基准元素x, 将数组Partation为两部分
        • 优化--降低最坏复杂性n方
          • 0. 如果数组足够小，则用简单排序算法对其排序
          • 1. 将数组切分为5个为一段的子序列，选取每个子序列中的中位数，将其换至最左端
            • for ( int i = 0; i<=(r-p-4)/5; i++ ) // i代表5长小组序号 { int s=p + 5*i; //s是小组起点 t=s + 4; //t是小组终点 for (int j=0; j<3; j++) bubble(s, t-j);//3次调用之后，中位数已经出现 swap(a, p+i, s+2); // }
          • 2. 在最左端的中位数部分，递归调用select，选出其中位数，作为划分基准x
            • Select(a, p, p+(r-p-4)/5, (r-p+6)/10);
      • 2. 如果左部分长度小于k，则在右数组，递归搜索a[q+1:n-1]。否则在左部分，递归搜索a[0:q]
        • j=i-p+1; //左子段长度 if (k<=j) return Select(a, p, i, k); else return Select(a, i+1, r, k-j);
    • 优化的数学证明
      • x至少比a[0: n-1] 中的3n/10-1个元素大
      • 推理
        • m=n/5，x所在组之前的m/2-1个组的中位数均小于x
        • 每组共有有3个元素小于x
        • 对x所在组，有2个元素<x
        • 3*(m/2-1)+2=3m/2-1=3n/10-1个元素小于x
      • 例子
        • 要求划分后的2个子数组长度至少缩减1/4, n=? 当n≥20时， (3n/10 -1) ≥ n/4: 40*(3n/10 -1) ≥ 40*(n/4), 12n-40 ≥ 10n, n ≥ 20
    • 复杂度
      • T(n)=O(n)
  • 平面最近点对
    • 给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小
    • 步骤
      • 0. 将所有点按照x坐标排序，找到中位数作为分割线
      • 1. 判断点的个数，1点则无穷，2点则求两点之间的距离, 三点则两两比较
        • 递归结束的标志
      • 2. d1 = 左半区间最近点对距离， d2 = 右半区间最近点对的距离， d = min{ d1, d2 }
        • closest(X, Z, Y,L,m,a,b,d);
        • closest(X, Z, Y,m+1,r,ar,br,dr);
        • if (dr<d) { a=ar; b=br; d=dr}
      • 3. 以左右区间垂直分割线为中心，纳入宽度为d的点共k个，其他的抛弃，形成数组Z
        • for (int i=L; i<=r; i++) if (y[i].x >m) z[g++]=y[i] else z[f++]=y[i];
        • int k=L; for (int i=L; i<=r; i++) if (fabs(Y[m].x-Y[i].x))<d Z[k++]=Y[i];
      • 4. 将数组Z按照y坐标排序
        • merge(Z,Y,L,m,r);
      • 5. 对数组Z进行线性扫描
        • 对点Z[i]，仅扫描y轴距离在d之内的点，并计算其距离dist(Z[i],Z[j])
          • for (int i=L; i<=k; i++) //搜索Z[L:k-1] { for (int j=i+1; j<k&&Z[j].y-Z[i].y <d; j++) { float dp=distance(Z[i],Z[j]); if (dp<d) { d=dp; a=X[Z[i].p], b=X[Z[j].p]; } } }
      • d = min(d,d3)
  • 循环赛问题