算法導(dǎo)論第四章——分治策略

在分治策略中，我們遞歸地求解一個(gè)問題，在每層遞歸中應(yīng)用如下三個(gè)步驟

分解：將問題劃分為一些子問題，子問題的形式和原問題一樣免钻，只是規(guī)模更小
解決：遞歸地求解出子問題，如果子問題規(guī)模足夠小崔拥，則停止遞歸直接求解
合并：將子問題的解組合成原問題的解

當(dāng)子問題足夠大极舔，需要遞歸求解時(shí)，我們稱之為遞歸情況握童，當(dāng)子問題足夠小，不需要遞歸時(shí)叛赚，我們稱之為基本情況澡绩。有時(shí)子問題與原問題不完全一樣，我們將這些子問題的求解看成合并步驟的一部分俺附。

1. 最大子數(shù)組問題

即給定一個(gè)數(shù)組肥卡，要求找出一個(gè)連續(xù)的子數(shù)組，使得這個(gè)子數(shù)組的和是所有子數(shù)組中最大的事镣。

采用分治策略的求解辦法

假定我們要尋找子數(shù)組 $A[low,high]$ 的最大子數(shù)組步鉴，使用分治技術(shù)意味著我們要將子數(shù)組劃分為規(guī)模盡量相等的兩個(gè)子數(shù)組，找到中間位置mid璃哟，然后考慮求解兩個(gè)子數(shù)組 $A[low,mid]$ 和 $A[mid+1,high]$ , $A[low..high]$ 的任何連續(xù)子數(shù)組 $A[i..j]$ 所處的位置必然是以下三種情況之一：

完全位于子數(shù)組 $A[low..mid]$ 中
完全位于子數(shù) $A[mid+1..high]$ 中
跨越了中點(diǎn)氛琢，即 $low<=i<=mid<j<=high$

故 $A[low..high]$ 的一個(gè)最大子數(shù)組必然是這三種子數(shù)組中和最大的一個(gè)。我們可以遞歸求解 $A[low..mid]$ 和 $A[mid+1,high]$ 的最大子數(shù)組随闪，然后找出跨越中點(diǎn)的最大子數(shù)組阳似，在三者中選取和最大者。

三種情況示例.jpg

我們可以很容易地在線性時(shí)間內(nèi)求出跨越中點(diǎn)的最大子數(shù)組铐伴。任何跨越重點(diǎn)的子數(shù)組都由兩個(gè)數(shù)組 $A[i..mid]和A[mid+1..j]$ 組成撮奏，因此我們只需求出左右兩邊分別從mid開始的最大子數(shù)組俏讹，再合并即可。函數(shù)返回包含有邊界即和的元組畜吊。
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)

如此泽疆，查找跨越中間最大子數(shù)組的時(shí)間復(fù)雜度為 $Θ(n)$

有了該查找算法，我們就可以設(shè)計(jì)求解最大子數(shù)組的分治算法代碼了：
python實(shí)現(xiàn)如下

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)

分治算法的分析

接下來玲献，我們建立一個(gè)遞歸式來描述該過程的運(yùn)行時(shí)間殉疼。我們先進(jìn)行簡化，假設(shè)原問題的規(guī)模為2的冪青自。
對n=1的基本情況株依， $T(1)=Θ(1)$
n>1時(shí)，花費(fèi)的時(shí)間為
$T(n) = 2T(n/2)+Θ(n)$ 延窜，因此該算法的時(shí)間復(fù)雜度為 $Θ(nlgn)$

2. 矩陣乘法的Strassen算法

常規(guī)的矩陣乘法需要 $Θ(n^3)$ 的時(shí)間恋腕，但使用Strassen算法，可以將時(shí)間優(yōu)化到 $Θ(n^{lg7}))$

簡單的分治算法

為簡單起見逆瑞，當(dāng)計(jì)算 $C = A×B$ 時(shí)荠藤，假定都為 $n*n$ 的矩陣，且 $n$ 為2的次冪
那么我們可以將每個(gè)矩陣都分解為4個(gè) $n/2 * n/2$ 的矩陣
那么可以將公式寫為

公式.PNG

這個(gè)公式等價(jià)于

公式2.png

我們可以用此公式設(shè)計(jì)出遞歸分支算法

偽代碼.jpg

在第五行的分解矩陣中获高，我們并不真正的創(chuàng)建子矩陣哈肖，二十使用下標(biāo)計(jì)算來指明一個(gè)子矩陣，因此分解僅需

Θ(1)

的時(shí)間念秧。

我們接下來進(jìn)行遞歸式的推倒淤井，設(shè)運(yùn)行時(shí)間為 $T(n)$
當(dāng)n=1時(shí)， $T(1)=Θ(1)$
在遞歸情況下摊趾，每次遞歸需要完成兩個(gè) $n/2$ 的乘法币狠，因此花費(fèi)的時(shí)間為 $T(n/2)$ ，共調(diào)用8詞遞歸砾层，因此時(shí)間為 $8T(n/2)$
我們還需進(jìn)行四次矩陣加法漩绵，總時(shí)間為 $Θ(n^2)$
因此總的運(yùn)行時(shí)間為
$T(n) = 8T(n/2)+Θ(n^2)$
解出的時(shí)間復(fù)雜度為 $T(n)=Θ(n^3)$
因此簡單分治并不由于通常的直接計(jì)算方法。

Strassen算法

該算法的核心是減少遞歸樹的寬度肛炮，即只遞歸進(jìn)行7次乘法止吐。
步驟如下:

1. 與簡單分治一樣，將矩陣分解為四個(gè)子矩陣侨糟，花費(fèi) $Θ(1)$ 的時(shí)間
2.創(chuàng)建十個(gè) $n/2$ 的子矩陣碍扔， $S1,S2...S10$ 用來保存步驟一中創(chuàng)建的兩個(gè)子矩陣的和或差，復(fù)雜度為 $Θ(n^2)$
3.使用步驟一中的子矩陣和步驟二中的子矩陣遞歸算出7個(gè)矩陣積 $P1,P2...P7$
4.通過 $Pi$ 矩陣的不同組合進(jìn)行加減運(yùn)算秕重，計(jì)算出C的子矩陣蕴忆，花費(fèi)時(shí)間 $Θ(n^2)$
得到的遞歸式為：

遞歸式.jpg

解出方程， $T(n) = Θ(n^{lg7})$
算法細(xì)節(jié)參見：
參考鏈接

3.使用代入法求解遞歸式

4.使用遞歸樹法求解遞歸式

這兩種方法并不常用悲幅，快進(jìn)到主方法求解遞歸式

5.用主方法求解遞歸式

主方法為如下形式的遞歸式提供了統(tǒng)一的解決辦法
$T(n) = aT(n/b)+f(n)$
其中 $a≥1$ 和 $b>1$ 是常數(shù)套鹅，f(n)是漸進(jìn)正函數(shù)站蝠，使用主方法只需要記住三種情況。
該遞歸式描述了將規(guī)模為n的問題分解為a個(gè)子問題卓鹿，每個(gè)子問題規(guī)模為n/b菱魔。而函數(shù)f(n)包含了問題分解和子問題解合并的代價(jià)。

主定理

若我們將 $n/b$ 解釋為 $int(n/b)$ 吟孙，那么 $T(n)$ 有如下漸進(jìn)界:

若對于某個(gè)常數(shù) $ε>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))$