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

2021 iThome 鐵人賽

DAY 8

自我挑戰組

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

13th鐵人賽自學筆記 algorithm

吳他，惟手熟爾

2021-09-19 14:34:24

1617 瀏覽

二分搜尋法(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)$
發現這個遞迴關係式符合關係式 $T(n)=aT(n/b)+f(n)$ ，可以使用主定理(master method)求解，代入 $n^{\log_ba}$ ，得到 $n^{\log_21}$ ，這個結果大於 $\Theta(1)$ (主方法case 2)，因此該遞迴式的解為 $\Theta(n^{log2^1}lg^{\varepsilon+1}n)$
$(\log_21 = 0)$ ，得到解 $\Theta({lg}n)$ 。

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，用 $\Theta(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)$ ，如同二分搜尋法的結果，得出的解為 $\Theta({lg}n)$ ，這個方法就稱為native recursive squaring。

費波那契數列

定義
$F(n) = \begin{array} \ 0 \ if \ n = 0 ,\\ 1 \ if \ n = 1,\\ F(n - 1) + F(n - 2), \ if \ n >=2, \end{array}$
時間複雜度 : $\Omega(\phi^n)$ , $\phi$ 為黃金比例常數， $https://chart.googleapis.com/chart?cht=tx&chl=%5Cphi%20%3D%20%5Cfrac%20%7B1%2B%20%5Csqrt%205%7D%202$
這是一個指數型的時間複雜度，而我們希望他可以式多項式的時間複雜度。

如果我們將費波那契數列的遞迴情況畫成一棵樹，會發現存在許多相同的子樹，也就是有許多情況不斷地重複發生，以至於浪費了許多時間，我們可以將計算過的結果放在一個陣列當中(動態規劃的想法)，此持我們在計算 $F(n)$ 時間就會是 $\Theta(n)$ (我們只需要知道前n項相加即可)。

native recursive squaring(樸素平方遞迴)的時間複雜度為 $\Theta({lg}n)$ ，如果我們將 $F(n) = \phi^n / \sqrt 5$ 取整數到與其最接近的整數，我們會發現其結果就是第n位的費波那契數。

但是在真實的機器中，這個方法是不可行的，原因是因為我們必須使用浮點數表示 $\phi$ 和 $\sqrt 5$ ，直接取整可能會有錯誤發生。

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

$\begin{pmatrix} F_{n+1}&F_n\\F_n&F_{n-1} \end{pmatrix}\quad =\begin{pmatrix} 1&1\\1&0 \end{pmatrix}^n\quad$
2*2的矩陣和2*2的矩陣進行乘法運算得出來的結果依然是2*2的矩陣，規模不會變大，我們使用分治法的出的時間複雜度依然會保持在 $\Theta({lg}n)$

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

基本情況(base): $=\begin{pmatrix} 1&1\\1&0 \end{pmatrix}^1\quad = \begin{pmatrix} F_2&F_1\\F_1&F_0 \end{pmatrix}\quad$
推遞步驟(step): $=\begin{pmatrix} F_{n+1}&F_n\\F_n&F_{n-1} \end{pmatrix}\quad =$ $\begin{pmatrix} F_{n}&F_{n - 1}\\F_{n-1}&F_{n-2} \end{pmatrix}\quad$ $\begin{pmatrix} 1&1\\1&0 \end{pmatrix}\quad =$ $\begin{pmatrix} 1&1\\1&0 \end{pmatrix}^{n - 1}\quad$
如果將n-1，就會具備從左式到右式這樣的特性，根據歸納假設。
我們可以試著將 $F_{n + 1}$ 結果展開，也就是求右式矩陣乘法展開的結果，會得到 $F_{n + 1}=F_n+F{n - 1}$ ，恰好為費波那契數的定義，使假設正確。

我們將上面進行結合，得到
$\begin{pmatrix} 1&1\\1&0 \end{pmatrix}^{n - 1}\quad$ $\begin{pmatrix} 1&1\\1&0 \end{pmatrix}\quad$ $=\begin{pmatrix} 1&1\\1&0 \end{pmatrix}^n\quad$

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

矩陣乘法(Matrix multiplication)

Input: $A = \begin{bmatrix} a_{ij}\end{bmatrix}$ , $B = \begin{bmatrix} b_{ij}\end{bmatrix}$ , $i,j = 1,2...,n$
Output: $C = \begin{bmatrix} c_{ij}\end{bmatrix} = A*B$

$C_{ij} =\sum_{k=1}^na_{ik}\ \ b_{kj}$
假設是一個2*2的矩陣乘法，矩陣C總共有4項需要計算，每一個項需要2步的計算
$\begin{pmatrix} a_{1,1}&a_{1,2}\\a_{2,1}&a_{2,2} \end{pmatrix}$ $\begin{pmatrix} b_{1,1}&b_{1,2}\\b_{2,1}&b_{2,2} \end{pmatrix} =$ $\begin{pmatrix} a_{1,1}b_{1,1} + a_{1,2}b_{2,1}& a_{1,1}b_{1,2} + a_{1,2}b_{2,2}\\ a_{2,1}b_{1,1} + a_{2,2}b_{2,2}& a_{2,1}b_{1,2} + a_{2,2}b_{2,2} \end{pmatrix}$

若有一個n*n的矩陣乘法。矩陣C需要 $n^2$ 項需要計算，每一項需要n步，整體複雜度為 $n^3$

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];
            }
        }
    }

我們使用分治法降低時間複雜度，每個矩陣有 $n^2$ 數字(因為是方陣)，上面分治法的想法都是將規模為n的問題分解成n/2的兩個子問題，我們希望一個n*n的矩陣可以轉化為兩個n/2*n/2規模的矩陣，我們可以使用分塊矩陣(block matrix)的想法

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

$\begin{pmatrix} a&b\\c&d \end{pmatrix}$ $\begin{pmatrix} e&f\\g&h \end{pmatrix}$ $= \begin{pmatrix} r&s\\t&u \end{pmatrix}$
我們可以得到以下的關係
$r = ae+bg$
$s = af+bh$
$t = ce+dg$
$u = cf+dh$

$a,b,c,d$ 我們將其視為A矩陣， $e,f,g,h$ 將其視為B矩陣， $r,s,t,u$ 將其視為C矩陣，我們要求的C矩陣的結果，就是將上面結果計算並組合之後就能夠得到，每一個字母我們可以想像成是一個n/2規模的矩陣，我們需要不斷的遞迴計算乘積，直到每一個字母是一個數字。

在上面這個例子中，我們可以得到我們需要進行8次的遞迴運算，也就是 $n^3$ ，以及4次的求和運算，將兩個矩陣相加所需要的時間複雜度是 $\Theta(n^2)$ ，矩陣加法的複雜度已經無法再減少了，目前矩陣乘法的總複雜度為:

$T(n) = 8T(n/2) + \Theta(n^2)$ ，發現這個遞迴關係式符合關係式 $T(n)=aT(n/b)+f(n)$ ，因此使用主定理來解出這個遞迴式
代入 $n^{\log_ba}$ 得到 $n^3$ ， $n^3>\Theta(n^2)$ ，屬於case 1.
因此結果為 $\Theta(n^{\log_ba})$ ，也就是 $\Theta(n^3)$

Strassen's algorithm

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

$\begin{pmatrix} a&b\\c&d \end{pmatrix}$ $\begin{pmatrix} e&f\\g&h \end{pmatrix}$ $=\begin{pmatrix} r&s\\t&u \end{pmatrix}$

$P_1 = a(f-h)$
$P_2 = (a+b)h$
$P_3 = (c+d)e$
$P_4 = d(g-e)$
$P_5 = (a+d)(e+h)$
$P_6 = (b-d)(g+h)$
$P_7 = (a-c)(e+f)$

我們可以在 $7T(n/2)$ 的時間完成這一些操作，之後我們將 $r,s,t,u$ 這四項元素用上面的符號進行表示:
$r = P_5 + P_4 - P_2 + P_6$
$s = P_1 + P_2$
$t = P_3 + P_4$
$u = P_5 + P_1 - P_3 - P_7$

我們可以確認看看這一些結果，以u作為例子
$u = P_5 + P_1 - P_3 - P_7 = (ae+ah+de+dh) + (af-ah) - (ce+de) - (ae+af-ce-cf)$
得到 $u = cf+dh$ ，會發現跟我們上方正常進行矩陣乘法運算的結果是相同的

這個演算法使用分治法的思路如下
Divide : 將A矩陣和B矩陣進行拆分，然後求得一些乘積項，也就是計算出所有的P，這一步需要 $\Theta(n^2)$

Conquer : 遞迴的方式處理每一個 $P_i$ ，得到7個乘積

Combine : 結合每一項P的結果，得出 $r,s,t,u$ ，需要 $\Theta(n^2)$

整個演算法的遞迴關係式為 $T(n) = 7T(n/2) + \Theta(n^2)$ ，發現這個遞迴關係式符合關係式 $T(n)=aT(n/b)+f(n)$ ，因此使用主定理來解出這個遞迴式
代入 $n^{\log_b^a}$ 得到 $n^{\ log2^7}$ , $\log_27 = 2.807$ ，屬於case 1.因此時間複雜度為 $\Theta(n^{2.807})$ ，比 $\Theta(n^3)$ 好，但不是最好的演算法，目前最好的矩陣乘法演算法為Coppersmith-Winograd，複雜度為 $\Theta(n^{2.376})$