算法导论第四章——分治策略

在分治策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤

分解：将问题划分为一些子问题，子问题的形式和原问题一样，只是规模更小
解决：递归地求解出子问题，如果子问题规模足够小，则停止递归直接求解
合并：将子问题的解组合成原问题的解

当子问题足够大，需要递归求解时，我们称之为递归情况，当子问题足够小，不需要递归时，我们称之为基本情况。有时子问题与原问题不完全一样，我们将这些子问题的求解看成合并步骤的一部分。

1. 最大子数组问题

即给定一个数组，要求找出一个连续的子数组，使得这个子数组的和是所有子数组中最大的。

采用分治策略的求解办法

假定我们要寻找子数组 $A[low,high]$ 的最大子数组，使用分治技术意味着我们要将子数组划分为规模尽量相等的两个子数组，找到中间位置mid，然后考虑求解两个子数组 $A[low,mid]$ 和 $A[mid+1,high]$ , $A[low..high]$ 的任何连续子数组 $A[i..j]$ 所处的位置必然是以下三种情况之一：

完全位于子数组 $A[low..mid]$ 中
完全位于子数 $A[mid+1..high]$ 中
跨越了中点，即 $low<=i<=mid<j<=high$

故 $A[low..high]$ 的一个最大子数组必然是这三种子数组中和最大的一个。我们可以递归求解 $A[low..mid]$ 和 $A[mid+1,high]$ 的最大子数组，然后找出跨越中点的最大子数组，在三者中选取和最大者。

三种情况示例.jpg

我们可以很容易地在线性时间内求出跨越中点的最大子数组。任何跨越重点的子数组都由两个数组 $A[i..mid]和A[mid+1..j]$ 组成，因此我们只需求出左右两边分别从mid开始的最大子数组，再合并即可。函数返回包含有边界即和的元组。
python代码描述如下:

inf = float("inf")
def findMaxCrossingSubArray(A,low,mid,high):
    leftSum = -inf
    sum = 0
    maxLeft = 0
    maxRight = 0
    for i in range(mid,low-1,-1):
        sum+=A[i]
        if sum>leftSum:
            leftSum = sum
            maxLeft = i
    rightSum = -inf
    sum = 0
    for j in range(mid+1,high+1):
        sum+=A[j]
        if sum>rightSum:
            rightSum = sum
            maxRight = j
    return (maxLeft,maxRight,leftSum+rightSum)

如此，查找跨越中间最大子数组的时间复杂度为 $Θ(n)$

有了该查找算法，我们就可以设计求解最大子数组的分治算法代码了：
python实现如下

def findMaxSumSubArray(A,low,high):
    if high==low:
        return (low,high,A[low])
    else:
        mid = (low+high)//2
        leftLow,leftHigh,leftSum = findMaxSumSubArray(A,low,mid)
        rightLow,rightHigh,rightSum = findMaxSumSubArray(A,mid+1,high)
        crossLow,crossHigh,crossSum  = findMaxCrossingSubArray(A,low,mid,high)
        if leftSum>=rightSum and rightSum>= crossSum:
            return (leftLow,leftHigh,leftSum)
        elif rightSum>=leftSum and rightSum>=crossSum:
            return (rightLow,rightHigh,rightSum)
        else:
            return (crossLow,crossHigh,crossSum)

分治算法的分析

接下来，我们建立一个递归式来描述该过程的运行时间。我们先进行简化，假设原问题的规模为2的幂。
对n=1的基本情况， $T(1)=Θ(1)$
n>1时，花费的时间为
$T(n) = 2T(n/2)+Θ(n)$ ，因此该算法的时间复杂度为 $Θ(nlgn)$

2. 矩阵乘法的Strassen算法

常规的矩阵乘法需要 $Θ(n^3)$ 的时间，但使用Strassen算法，可以将时间优化到 $Θ(n^{lg7}))$

简单的分治算法

为简单起见，当计算 $C = A×B$ 时，假定都为 $n*n$ 的矩阵，且 $n$ 为2的次幂
那么我们可以将每个矩阵都分解为4个 $n/2 * n/2$ 的矩阵
那么可以将公式写为

公式.PNG

这个公式等价于

公式2.png

我们可以用此公式设计出递归分支算法

伪代码.jpg

在第五行的分解矩阵中，我们并不真正的创建子矩阵，二十使用下标计算来指明一个子矩阵，因此分解仅需

Θ(1)

的时间。

我们接下来进行递归式的推倒，设运行时间为 $T(n)$
当n=1时， $T(1)=Θ(1)$
在递归情况下，每次递归需要完成两个 $n/2$ 的乘法，因此花费的时间为 $T(n/2)$ ，共调用8词递归，因此时间为 $8T(n/2)$
我们还需进行四次矩阵加法，总时间为 $Θ(n^2)$
因此总的运行时间为
$T(n) = 8T(n/2)+Θ(n^2)$
解出的时间复杂度为 $T(n)=Θ(n^3)$
因此简单分治并不由于通常的直接计算方法。

Strassen算法

该算法的核心是减少递归树的宽度，即只递归进行7次乘法。
步骤如下:

1. 与简单分治一样，将矩阵分解为四个子矩阵，花费 $Θ(1)$ 的时间
2.创建十个 $n/2$ 的子矩阵， $S1,S2...S10$ 用来保存步骤一中创建的两个子矩阵的和或差，复杂度为 $Θ(n^2)$
3.使用步骤一中的子矩阵和步骤二中的子矩阵递归算出7个矩阵积 $P1,P2...P7$
4.通过 $Pi$ 矩阵的不同组合进行加减运算，计算出C的子矩阵，花费时间 $Θ(n^2)$
得到的递归式为：

递归式.jpg

解出方程， $T(n) = Θ(n^{lg7})$
算法细节参见：
参考链接

3.使用代入法求解递归式

4.使用递归树法求解递归式

这两种方法并不常用，快进到主方法求解递归式

5.用主方法求解递归式

主方法为如下形式的递归式提供了统一的解决办法
$T(n) = aT(n/b)+f(n)$
其中 $a≥1$ 和 $b>1$ 是常数，f(n)是渐进正函数，使用主方法只需要记住三种情况。
该递归式描述了将规模为n的问题分解为a个子问题，每个子问题规模为n/b。而函数f(n)包含了问题分解和子问题解合并的代价。

主定理

若我们将 $n/b$ 解释为 $int(n/b)$ ，那么 $T(n)$ 有如下渐进界:

若对于某个常数 $ε>0$ ，有 $f(n)=O(n^{logb^{a-ε}})$ ，则 $T(n)=Θ(n^{logb^a})$
若 $f(n)=Θ(n^{logb^a})$ ，则 $T(n)=Θ(n^{logb^a}lgn)$
若 $f(n) = Ω(n^{logb^{a+ε}})$ ，且对于 $c<1$ 和足够大的n有 $af(n/b)<=cf(n),则T(n) = Θ(f(n))$