第四章 分治政策

Divide-Conquer-Combine

4.1 最大子數組問題

FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high) 
    /*
    接受數組A和下表low,mid,high為輸入，
    傳回一個下标元組劃定跨越種點的最大子數組的邊界，并傳回最大子數組中值的和
    */
left-sum = -∞
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > left - sum
        left-sum = sum
        max-left = i
right-sum = -∞
sum = 0
for j = mid + 1 to high
    sum = sum + A[j]
    if sum > right-sum
        right-sum = sum
        max-right = j
return(max-left, max-right, left-sum + right-sum)

FIND-MAXIMUM-SUBARRAY(A,low,high) //求出A[1...n]的最大子數組
if high == low
    return (low,high,A[low])
else mid = (low + high)/2
    (left-low, left-high, left-sum) = 
    	FIND-MAXIMUM-SUBARRAY(A,low,mid)
    (right-low, right-high, right-sum) = 
    	FIND-MAXIMUM-SUBARRAY(A,mid+1,high)
    (cross-low, cross-high, cross-sum) = 
    	FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
    if left-sum >= cross-sum and right-sum >= cross-sum
        return(left-low, left-high, left-sum)
    else right-sum >= cross-sum and right-sum >= cross-sum
        return(right-low, right-high, right-sum)
    else return(cross-low, cross-high, cross-sum)

           

4.2 矩陣乘法的Strassen算法

正常算法花費Θ(n3)，Strassen算法花費Θ(nlg7)≈Θ(n^2.81)

基本思想：減少多餘的乘法，把乘法變成乘法+加法

4.3 代入法求解遞歸式

步驟

1. 猜測解的形式
2. 用數學歸納法求出解種的常數，并證明解是正确的

4.4 遞歸樹方法求解遞歸式

将遞歸式轉換成一棵樹，其節點表示不同層次的遞歸調用産生的代價。然後采用邊界和技巧來求解遞歸式。

4.5 主方法求解遞歸式

求解形式如 T ( n ) = a T ( n / b ) + f ( n ) T(n)=aT(n/b)+f(n) T(n)=aT(n/b)+f(n)遞歸式的界

4.5 主方法求解遞歸式

求解形式如 T ( n ) = a T ( n / b ) + f ( n ) T(n)=aT(n/b)+f(n) T(n)=aT(n/b)+f(n)遞歸式的界