iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 8

Day-8 Divide-and-Conquer-3 : 二分搜尋法, 費波那契數列, Strassen’s演算法

二分搜尋法(Binary Search)

前提,在一個已經排序完成的A陣列中
Divide : 元素x和A陣列的中間元素進行比較
Conquer : 在其中一個子陣列中進行遞迴,如果x小於A陣列的中間元素,就在左子陣列進行遞迴。
Combine : 沒有
遞迴關係式: https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20T(%5Cfrac%20n%202)%20%2B%20%5CTheta(1)
發現這個遞迴關係式符合關係式https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n),可以使用主定理(master method)求解,代入https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7B%5Clog_ba%7D,得到https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7B%5Clog_21%7D,這個結果大於https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(1)(主方法case 2),因此該遞迴式的解為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E%7Blog2%5E1%7Dlg%5E%7B%5Cvarepsilon%2B1%7Dn)
https://chart.googleapis.com/chart?cht=tx&chl=(%5Clog_21%20%3D%200),得到解https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(%7Blg%7Dn)

int binary_search(vector<int> &array, int min, int max, int target)
{
    int mid = 0;
    if (max > min)
    {
        mid = start + (end - start)/2
        if(array[mid] == target)
        {
            return array[mid];
        }
        if (target < array[mid])
        {
            return binary_search(array, min, mid - 1, target);
        }
        else if(target > array[mid])
        {
            return binary_search(array, mid + 1, max, target);
        }
    }
    return -1;
}

x的n次方

正常一般情況,要計算x的n次方,即為將x * x * x....進行n次,每一次的乘法需要一個常數時間c,總時間為cn,用https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n)進行表示。

我們引入分治法的想法,去解決這個問題,我們可以把這個問題進行分解
https://chart.googleapis.com/chart?cht=tx&chl=x%5En%20%3D%20x%5E%7B%5Cfrac%20n%202%7D%20%2B%20x%5E%7B%5Cfrac%20n%202%7D,當n為偶數時,如果我們得知https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cfrac%20n%202%7D的結果,只剩下https://chart.googleapis.com/chart?cht=tx&chl=x%5E%7B%5Cfrac%20n%202%7D%20%2B%20x%5E%7B%5Cfrac%20n%202%7D需要計算,這需要一個常數時間,因此,複雜度就會變成原來的一半,將這個遞迴關係寫出
https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%20T(%5Cfrac%20n%202)%20%2B%20%5CTheta(1),如同二分搜尋法的結果,得出的解為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(%7Blg%7Dn),這個方法就稱為native recursive squaring。

費波那契數列

定義
https://chart.googleapis.com/chart?cht=tx&chl=F(n)%20%3D%20%20%20%5Cbegin%7Barray%7D%20%5C%200%20%5C%20if%20%5C%20n%20%3D%200%20%2C%5C%5C%20%201%20%5C%20if%20%5C%20n%20%3D%201%2C%5C%5C%20F(n%20-%201)%20%2B%20F(n%20-%202)%2C%20%5C%20if%20%5C%20n%20%3E%3D2%2C%20%20%5Cend%7Barray%7D
時間複雜度 : https://chart.googleapis.com/chart?cht=tx&chl=%5COmega(%5Cphi%5En), https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi為黃金比例常數,https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi%20%3D%20%5Cfrac%20%7B1%2B%20%5Csqrt%205%7D%202
這是一個指數型的時間複雜度,而我們希望他可以式多項式的時間複雜度。

如果我們將費波那契數列的遞迴情況畫成一棵樹,會發現存在許多相同的子樹,也就是有許多情況不斷地重複發生,以至於浪費了許多時間,我們可以將計算過的結果放在一個陣列當中(動態規劃的想法),此持我們在計算https://chart.googleapis.com/chart?cht=tx&chl=F(n)時間就會是https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n)(我們只需要知道前n項相加即可)。

native recursive squaring(樸素平方遞迴)的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(%7Blg%7Dn),如果我們將https://chart.googleapis.com/chart?cht=tx&chl=F(n)%20%3D%20%5Cphi%5En%20%2F%20%5Csqrt%205取整數到與其最接近的整數,我們會發現其結果就是第n位的費波那契數。

但是在真實的機器中,這個方法是不可行的,原因是因為我們必須使用浮點數表示https://chart.googleapis.com/chart?cht=tx&chl=%5Cphihttps://chart.googleapis.com/chart?cht=tx&chl=%5Csqrt%205,直接取整可能會有錯誤發生。

我們可以利用費波那契數的特性,來使用平方遞迴

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%20F_%7Bn%2B1%7D%26F_n%5C%5CF_n%26F_%7Bn-1%7D%20%5Cend%7Bpmatrix%7D%5Cquad%20%3D%5Cbegin%7Bpmatrix%7D%201%261%5C%5C1%260%20%5Cend%7Bpmatrix%7D%5En%5Cquad
2*2的矩陣和2*2的矩陣進行乘法運算得出來的結果依然是2*2的矩陣,規模不會變大,我們使用分治法的出的時間複雜度依然會保持在https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(%7Blg%7Dn)


下面使用數學歸納法進行證明:

  • 基本情況(base): https://chart.googleapis.com/chart?cht=tx&chl=%3D%5Cbegin%7Bpmatrix%7D%201%261%5C%5C1%260%20%5Cend%7Bpmatrix%7D%5E1%5Cquad%20%3D%20%5Cbegin%7Bpmatrix%7D%20F_2%26F_1%5C%5CF_1%26F_0%20%5Cend%7Bpmatrix%7D%5Cquad
  • 推遞步驟(step): https://chart.googleapis.com/chart?cht=tx&chl=%3D%5Cbegin%7Bpmatrix%7D%20F_%7Bn%2B1%7D%26F_n%5C%5CF_n%26F_%7Bn-1%7D%20%5Cend%7Bpmatrix%7D%5Cquad%20%3D https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%20F_%7Bn%7D%26F_%7Bn%20-%201%7D%5C%5CF_%7Bn-1%7D%26F_%7Bn-2%7D%20%5Cend%7Bpmatrix%7D%5Cquad https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%201%261%5C%5C1%260%20%5Cend%7Bpmatrix%7D%5Cquad%20%3D https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%201%261%5C%5C1%260%20%5Cend%7Bpmatrix%7D%5E%7Bn%20-%201%7D%5Cquad
    如果將n-1,就會具備從左式到右式這樣的特性,根據歸納假設。
    我們可以試著將https://chart.googleapis.com/chart?cht=tx&chl=F_%7Bn%20%2B%201%7D結果展開,也就是求右式矩陣乘法展開的結果,會得到https://chart.googleapis.com/chart?cht=tx&chl=F_%7Bn%20%2B%201%7D%3DF_n%2BF%7Bn%20-%201%7D,恰好為費波那契數的定義,使假設正確。

我們將上面進行結合,得到
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%201%261%5C%5C1%260%20%5Cend%7Bpmatrix%7D%5E%7Bn%20-%201%7D%5Cquad https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%201%261%5C%5C1%260%20%5Cend%7Bpmatrix%7D%5Cquad https://chart.googleapis.com/chart?cht=tx&chl=%3D%5Cbegin%7Bpmatrix%7D%201%261%5C%5C1%260%20%5Cend%7Bpmatrix%7D%5En%5Cquad

根據數學歸納法,證明完畢。

矩陣乘法(Matrix multiplication)

Input: https://chart.googleapis.com/chart?cht=tx&chl=A%20%3D%20%5Cbegin%7Bbmatrix%7D%20a_%7Bij%7D%5Cend%7Bbmatrix%7D, https://chart.googleapis.com/chart?cht=tx&chl=B%20%3D%20%5Cbegin%7Bbmatrix%7D%20b_%7Bij%7D%5Cend%7Bbmatrix%7D, https://chart.googleapis.com/chart?cht=tx&chl=i%2Cj%20%3D%201%2C2...%2Cn
Output: https://chart.googleapis.com/chart?cht=tx&chl=C%20%3D%20%5Cbegin%7Bbmatrix%7D%20c_%7Bij%7D%5Cend%7Bbmatrix%7D%20%3D%20A*B

https://chart.googleapis.com/chart?cht=tx&chl=C_%7Bij%7D%20%3D%5Csum_%7Bk%3D1%7D%5Ena_%7Bik%7D%5C%20%5C%20b_%7Bkj%7D
假設是一個2*2的矩陣乘法,矩陣C總共有4項需要計算,每一個項需要2步的計算
https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%20a_%7B1%2C1%7D%26a_%7B1%2C2%7D%5C%5Ca_%7B2%2C1%7D%26a_%7B2%2C2%7D%20%5Cend%7Bpmatrix%7D https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%20b_%7B1%2C1%7D%26b_%7B1%2C2%7D%5C%5Cb_%7B2%2C1%7D%26b_%7B2%2C2%7D%20%5Cend%7Bpmatrix%7D%20%3D https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%20a_%7B1%2C1%7Db_%7B1%2C1%7D%20%2B%20a_%7B1%2C2%7Db_%7B2%2C1%7D%26%20a_%7B1%2C1%7Db_%7B1%2C2%7D%20%2B%20a_%7B1%2C2%7Db_%7B2%2C2%7D%5C%5C%20a_%7B2%2C1%7Db_%7B1%2C1%7D%20%2B%20a_%7B2%2C2%7Db_%7B2%2C2%7D%26%20a_%7B2%2C1%7Db_%7B1%2C2%7D%20%2B%20a_%7B2%2C2%7Db_%7B2%2C2%7D%20%5Cend%7Bpmatrix%7D

若有一個n*n的矩陣乘法。矩陣C需要https://chart.googleapis.com/chart?cht=tx&chl=n%5E2項需要計算,每一項需要n步,整體複雜度為https://chart.googleapis.com/chart?cht=tx&chl=n%5E3

int main(void)
{
    int A[2][2] = {{2, 3}, {4, 5}};
    int B[2][2] = {{6, 7}, {8, 9}};
    int C[2][2] = {{0, 0}, {0, 0}};

    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
            }
        }
    }

我們使用分治法降低時間複雜度,每個矩陣有https://chart.googleapis.com/chart?cht=tx&chl=n%5E2數字(因為是方陣),上面分治法的想法都是將規模為n的問題分解成n/2的兩個子問題,我們希望一個n*n的矩陣可以轉化為兩個n/2*n/2規模的矩陣,我們可以使用分塊矩陣(block matrix)的想法


這個例子我們將4*4的矩陣看做4個2*2的矩陣,也就是將n*n的矩陣拆分成數個n/2*n/2的矩陣

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%20a%26b%5C%5Cc%26d%20%5Cend%7Bpmatrix%7D https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%20e%26f%5C%5Cg%26h%20%5Cend%7Bpmatrix%7D https://chart.googleapis.com/chart?cht=tx&chl=%3D%20%5Cbegin%7Bpmatrix%7D%20r%26s%5C%5Ct%26u%20%5Cend%7Bpmatrix%7D
我們可以得到以下的關係
https://chart.googleapis.com/chart?cht=tx&chl=r%20%3D%20ae%2Bbg
https://chart.googleapis.com/chart?cht=tx&chl=s%20%3D%20af%2Bbh
https://chart.googleapis.com/chart?cht=tx&chl=t%20%3D%20ce%2Bdg
https://chart.googleapis.com/chart?cht=tx&chl=u%20%3D%20cf%2Bdh

https://chart.googleapis.com/chart?cht=tx&chl=a%2Cb%2Cc%2Cd我們將其視為A矩陣,https://chart.googleapis.com/chart?cht=tx&chl=e%2Cf%2Cg%2Ch將其視為B矩陣,https://chart.googleapis.com/chart?cht=tx&chl=r%2Cs%2Ct%2Cu將其視為C矩陣,我們要求的C矩陣的結果,就是將上面結果計算並組合之後就能夠得到,每一個字母我們可以想像成是一個n/2規模的矩陣,我們需要不斷的遞迴計算乘積,直到每一個字母是一個數字。

在上面這個例子中,我們可以得到我們需要進行8次的遞迴運算,也就是https://chart.googleapis.com/chart?cht=tx&chl=n%5E3,以及4次的求和運算,將兩個矩陣相加所需要的時間複雜度是https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E2),矩陣加法的複雜度已經無法再減少了,目前矩陣乘法的總複雜度為:

https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%208T(n%2F2)%20%2B%20%5CTheta(n%5E2),發現這個遞迴關係式符合關係式https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n),因此使用主定理來解出這個遞迴式
代入https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7B%5Clog_ba%7D得到https://chart.googleapis.com/chart?cht=tx&chl=n%5E3https://chart.googleapis.com/chart?cht=tx&chl=n%5E3%3E%5CTheta(n%5E2),屬於case 1.
因此結果為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E%7B%5Clog_ba%7D),也就是https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E3)

Strassen's algorithm

這個想法的思路為,我們必須繞過這些乘法,也就是減少乘法發生的次數,上面這個例子中,我們需要進行8次,需要進行8次乘法運算並加總才能夠得到C,我們嘗試減少乘法發生的次數,以加快矩陣乘法的速度。在這個演算法中,我們可以讓乘法發生的次數降低到7次。

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%20a%26b%5C%5Cc%26d%20%5Cend%7Bpmatrix%7D https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Bpmatrix%7D%20e%26f%5C%5Cg%26h%20%5Cend%7Bpmatrix%7D https://chart.googleapis.com/chart?cht=tx&chl=%3D%5Cbegin%7Bpmatrix%7D%20r%26s%5C%5Ct%26u%20%5Cend%7Bpmatrix%7D

https://chart.googleapis.com/chart?cht=tx&chl=P_1%20%3D%20a(f-h)
https://chart.googleapis.com/chart?cht=tx&chl=P_2%20%3D%20(a%2Bb)h
https://chart.googleapis.com/chart?cht=tx&chl=P_3%20%3D%20(c%2Bd)e
https://chart.googleapis.com/chart?cht=tx&chl=P_4%20%3D%20d(g-e)
https://chart.googleapis.com/chart?cht=tx&chl=P_5%20%3D%20(a%2Bd)(e%2Bh)
https://chart.googleapis.com/chart?cht=tx&chl=P_6%20%3D%20(b-d)(g%2Bh)
https://chart.googleapis.com/chart?cht=tx&chl=P_7%20%3D%20(a-c)(e%2Bf)

我們可以在https://chart.googleapis.com/chart?cht=tx&chl=7T(n%2F2)的時間完成這一些操作,之後我們將https://chart.googleapis.com/chart?cht=tx&chl=r%2Cs%2Ct%2Cu這四項元素用上面的符號進行表示:
https://chart.googleapis.com/chart?cht=tx&chl=r%20%3D%20P_5%20%2B%20P_4%20-%20P_2%20%2B%20P_6
https://chart.googleapis.com/chart?cht=tx&chl=s%20%3D%20P_1%20%2B%20P_2
https://chart.googleapis.com/chart?cht=tx&chl=t%20%3D%20P_3%20%2B%20P_4
https://chart.googleapis.com/chart?cht=tx&chl=u%20%3D%20P_5%20%2B%20P_1%20-%20P_3%20-%20P_7

我們可以確認看看這一些結果,以u作為例子
https://chart.googleapis.com/chart?cht=tx&chl=u%20%3D%20P_5%20%2B%20P_1%20-%20P_3%20-%20P_7%20%3D%20(ae%2Bah%2Bde%2Bdh)%20%2B%20(af-ah)%20-%20(ce%2Bde)%20-%20(ae%2Baf-ce-cf)
得到https://chart.googleapis.com/chart?cht=tx&chl=u%20%3D%20cf%2Bdh,會發現跟我們上方正常進行矩陣乘法運算的結果是相同的

這個演算法使用分治法的思路如下
Divide : 將A矩陣和B矩陣進行拆分,然後求得一些乘積項,也就是計算出所有的P,這一步需要https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E2)

Conquer : 遞迴的方式處理每一個https://chart.googleapis.com/chart?cht=tx&chl=P_i,得到7個乘積

Combine : 結合每一項P的結果,得出https://chart.googleapis.com/chart?cht=tx&chl=r%2Cs%2Ct%2Cu,需要https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E2)

整個演算法的遞迴關係式為https://chart.googleapis.com/chart?cht=tx&chl=T(n)%20%3D%207T(n%2F2)%20%2B%20%5CTheta(n%5E2),發現這個遞迴關係式符合關係式https://chart.googleapis.com/chart?cht=tx&chl=T(n)%3DaT(n%2Fb)%2Bf(n),因此使用主定理來解出這個遞迴式
代入https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7B%5Clog_b%5Ea%7D得到https://chart.googleapis.com/chart?cht=tx&chl=n%5E%7B%5C%20log2%5E7%7D,https://chart.googleapis.com/chart?cht=tx&chl=%5Clog_27%20%3D%202.807,屬於case 1.因此時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E%7B2.807%7D),比https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E3)好,但不是最好的演算法,目前最好的矩陣乘法演算法為Coppersmith-Winograd,複雜度為https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(n%5E%7B2.376%7D)

參考資料: Introduction to algorithms 3rd


上一篇
Day-7 Divide-and-Conquer-2 : 求解遞迴式
下一篇
Day-9 Divide-and-Conquer-4 : Quicksort, 隨機化Quicksort
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言