Algorithm

算法分析之分治算法

Posted by Surflyan on 2017-07-04

1. 基本原理

经验告诉我们，小规模问题的解通常比大规模问题的解更容易得到，所以，在面对一个大规模问题时，可以考虑转换为几个具有相同形式的子问题来求解。实践证明，这种分而治之的策略简单而实用。

2. 适用前提

  1. 问题的规模缩小到一定程度可以轻易解决
  2. 问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
  3. 利用该问题分解出的子问题的解可以合并为该问题的解
  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

3. 处理步骤

划分 ： 将原问题分解成一些子问题，子问题在形式上与原问题相同。
递归求解 ：递归调用设计中的算法求解这些子问题。若递归调用时子问题的规模足够小，可以直接给出子问题的解。
合并 ：将子问题的解合并成原问题的解。

4. 复杂度分析

划分阶段的复杂度为 D(n) , 递归求解阶段的复杂度为 aT（n/b）， 合并阶段复杂度C(n);
可以得到分治算法递归方程：

T(n)=Θ(1)                   n≤c
T(n)=aT(n/b)+ D(n) +C(n)    n>c

5. 实例分析

通过 Strassen矩阵乘法 和 线性时间选择算法 两个实例来进一步理解分治算法，以及降低复杂度的两个方向。

5.1 Strassen矩阵乘法

输入： nn的矩阵X和Y
输出： X和Y的乘积XY=XY;
矩阵乘法公式：${z{ij}} = \sum{k=1}^n { {x{ik} }{ y{kj} } } $，时间复杂度为$\Theta (n^3)$。
考虑分治算法处理该问题，矩阵X，Y，XY都可以分成如下四个矩阵：

采用上述分块矩阵的做法，递归调用8次，时间复杂度仍然为$\Theta (n^3)$。
Strassen首先观察到矩阵乘法具有如下的特征：

因此，分治算法的递归求解阶段只需求解7个规模为n/2的子问题。
该算法时间复杂度约为$\Theta (n^{2.81})$

5.2 线性时间选择算法

中位数的线性时间选择算法，经数十年前人的努力，证明了从n个数中选取中位数需要的比较操作次数介于 1.5n 到 5.43n 之间。
问题：
输入： n个(不同)数构成的集合X,整数i,其中1≤i≤n
输出： x∈X使得X中恰有i-1个元素小于x

  1. 分组，每组5个数 最后一组可能少于5个数
  2. 将每组数分别用InsertionSort排序 选出每组元素的中位数
  3. 递归调用算法求得这些中位数的中位数(MoM)
  4. 用MoM完成划分，A={x|x∈X，且x＜Mon};B={x|x∈X，且x=Mon};C={x|x∈X，且x＞Mon}；
  5. 设x是中位数的中位数(MoM),划分完成后其下标为k
    • 如果i=k,则返回x 、
    • 如果i<k,则在A中递归选取第i-大的数
    • 如果i>k,则在C中递归选取第(i-k)-大的数

算法：
Input: 数组A[1:n], 1≤i≤n
Output: A[1:n]中的第i-大的数

 for  j=1   to  n/5
       InsertSort(A[(j-1)*5+1 :(j-1)*5+5]);
       swap(A[j], A[[(j-1)*5+3]);
x=Select(A[1: n/5],  n/10 );
k=partition(A[1:n], x);
if   k=i  then   return x;
else if  k>i  then
    return  Select(A[1:k-1],i);
else
   retrun Select(A[k+1:n],i-k);

可以发现，在A或C上求解子问题时算法至少剪除[ $\frac{3n}{10}$] 的数据。时间复杂度T(n)=Θ(n)

6. 总结

  • 实例一：启示我们，应该观察问题的解的构成，尽可能减少要求解的子问题的个数，从而降低复杂度。
  • 实例二：实质是一种基于剪枝搜索方法的分治算法。 关键在于每回递归求解不论在何种情况下都能剪除至少为n的常数因子个数据。

>
请多多指教！

CATALOG
    FEATURED TAGS
    Algorithm
    <