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)$
发现这个递回关系式符合关系式 $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})$