算法和數(shù)據(jù)結構

[TOC]

算法

函數(shù)的增長

漸近記號

用來描述算法漸近運行時間的記號蒂秘，根據(jù)定義域為自然數(shù)集$N={0, 1, 2, \cdots}$的函數(shù)來定義褒链。這樣的記號對描述最壞情況運行時間函數(shù)$T(n)$是方便的，因為該函數(shù)通常只定義在整數(shù)輸入規(guī)模上啊终。

$\Theta$記號

對一個給定的函數(shù)$g(n)$镜豹，用$\Theta(g(n))$來表示一下函數(shù)的集合：
$$\Theta(g(n)) = {f(n):存在正常量c_1、c_2和c_0蓝牲，使得對所有n\geq n_0趟脂，有0\leq c_1g(n)\leq f(n)\leq c_2g(n)}$$

若存在正常量$c_1$和$c_2$使得對足夠大的$n$，函數(shù)$f(n)$能“夾入”$c_1g(n)$與$c_2g(n)$之間例衍，則$f(n)$屬于集合$\Theta(g(n))$昔期，因為$\Theta(g(n))$是一個集合已卸，所以可以記“$f(n)\in \Theta(g(n))$”，以指出$f(n)$是$\Theta(g(n))$的成員硼一。作為替代累澡，我們通常記“$f(n)= Theta(g(n))$”以表達相同的概念。

我們稱$g(n)$是$f(n)$的一個漸進緊確界(asymptotically tight bound)般贼。

一般來說愧哟，對任意多項式$p(n) = \sum_{i=1}^n aⁱⁿi$，其中$a^{i$為常量且$a}d > 0$哼蛆，我們有$p(n) = \Theta(n^d)$蕊梧。

因為任意常量是一個0階多項式，所以可以把任意常量函數(shù)表示成$\Theta(n^0)$或者$\Theta(1)$腮介。

$O$記號

$\Theta$記號漸近地給出一個函數(shù)的上界和下界望几。當只有一個漸進上界時，使用$O$記號萤厅。對于給定的函數(shù)$g(n)$橄抹，用$O(g(n))$來表示以下函數(shù)的集合：
$$O(g(n)) = {f(n)：存在常量c和n_0，使得對所有n\geq n_0時惕味，有0\leq f(n) \leq cg(n)}$$

$\Omega$記號

正如$O$記號提供了一個函數(shù)的漸近上界楼誓，$\Omega$記號提供了漸近下界。對于給定的函數(shù)$g(n)$名挥，用$\Omega(g(n))$來表示以下函數(shù)的集合：
$$\Omega(g(n)) = {f(n)：存在正常量c和n_0疟羹，使得對所有n\geq n_0時，有0\leq cg(n)\leq f(n)}$$

漸近記號

<mark>定理3.1：對任意兩個函數(shù)$f(n)$和$g(n)$禀倔，我們有$f(n)=\Theta g(n)$榄融，當且僅當：$f(n)=O g(n)$且$f(n)=\Omega g(n)$。</mark>

$o$記號

由$O$記號提供的漸近上界可能是也可能不是漸近緊確的救湖。界$2n^2=O g(n^2)$是漸近緊確的愧杯，但是界$2n=O g(n^2)$卻不是。我們使用$o$記號來表示一個非漸進緊確的上界鞋既。

形式地定義$o(g(n))$為以下集合：$$o(g(n))={f(n):對任意正常量c>0,存在常量n_0>0,使得對所有n>n_0,有0\leq f(n) <cg(n)}$$

$O$記號與$o$記號的定義類似力九。主要區(qū)別在于是$f(n)=O(g(n))$中，界$0\leq f(n) \leq cg(n) $對某個常量$c>0$成立邑闺，但在$f(n)=o(g(n))$中跌前，界$0\leq f(n) <cg(n) $對所有常量$c>0$都成立。直觀上陡舅，在$o$記號中培廓，當$n$趨于無窮時刁品，函數(shù)$f(n)$相對于$g(n)$來說變得微不足道了弦聂，即：
$$\lim_{n \to \infty} \frac{f(n)}{g(n)}=0 $$

$\omega$記號

$\omega$記號與$\Omega$記號的關系類似于$o$與$O$的關系运授。我們使用$\omega$來定義一個非漸近緊確的下界。定義它的一種方式是：
$$f(n) \in \omega g(n)\ 當且僅當\ g(n) \in o(f(n))$$
然而我們形式化地定義$f(n)=\omega(g(n))$為以下集合：
$$\omega(g(n)) = {f(n):對任意正常量c>0,存在常量n_0>0,使得對所有的n\geq n_0時，有0\leq cg(n)<f(n)}$$

關系$f(n)=\omega(g(n))$蘊含著：
$$\lim_{n \to \infty} \frac{f(n)}{g(n)}=\infty$$
也就是說，如果這個極限存在，當$n$趨于無窮時败徊，$f(n)$相對于$g(n)$來說變得任意大了。

比較各種函數(shù)
實數(shù)的許多關鍵性質(zhì)也適用于漸近比較掏缎。下面假定$f(n)$和$g(n)$漸近為正皱蹦。
傳遞性
$$f(n)=\Theta(g(n))\ 且\ g(n)=\Theta(g(n)) \quad 蘊含f(n)=\Theta(h(n))$$
$$f(n)=O(g(n))\ 且\ g(n)=O(g(n)) \quad 蘊含f(n)=O(h(n))$$
$$f(n)=\Omega(g(n))\ 且\ g(n)=\Omega(g(n)) \quad 蘊含f(n)=\Omega(h(n))$$
$$f(n)=o(g(n))\ 且\ g(n)=o(g(n)) \quad 蘊含f(n)=o(h(n))$$
$$f(n)=\omega(g(n))\ 且\ g(n)=\omega(g(n)) \quad 蘊含f(n)=\omega(h(n))$$
自反性
$$f(n)=\Theta(f(n))$$
$$f(n)=O(f(n))$$
$$f(n)=\Omega(f(n))$$
對稱性
$$f(n)=\Theta(g(n))\ 當且僅當\ g(n)=\Theta(f(n))$$
轉置對稱性
$$f(n)=O(g(n))\ 當且僅當\ g(n)=\Omega(f(n))$$
$$f(n)=o(g(n))\ 當且僅當\ g(n)=\omega(f(n))$$
因為這些性質(zhì)對漸近記號成立，所以可以在兩個函數(shù)$f$和$g$的漸近比較和兩個實數(shù)a和b的比較之間做一種類比眷蜈。
$$f(n)=O(g(n))\ 類似于\ a \leq b$$
$$f(n)=\Omega(g(n))\ 類似于\ a \geq b$$
$$f(n)=\Theta(g(n))\ 類似于\ a = b$$
$$f(n)=o(g(n))\ 類似于\ a <b$$
$$f(n)=\omega (g(n))\ 類似于\ a >b$$

<mark>三分性 ? 對任意兩個實數(shù)a和b沪哺，下列三種情況恰有一種必須成立：$a<b,\ a=b,\ a>b$</mark>

雖然任意兩個時序都可以進行比較，但是不是所有的函數(shù)都可漸近比較酌儒。也就是說辜妓，對兩個函數(shù)$f(n)$和$g(n)$，也許$f(n)=O(g(n))$和$f(n)=\Omega(g(n))$都不成立忌怎。

標準記號與常用函數(shù)

單調(diào)性

若$m\leq n$蘊含$f(m) \leq f(n)$籍滴，則函數(shù)$f(n)$是單調(diào)遞增的。類似的榴啸，若$m\leq n$蘊含$f(m) \geq f(n)$孽惰，則函數(shù)$f(n)$是單調(diào)遞減的。若$m<n$蘊含$f(m) < f(n)$鸥印，則函數(shù)$f(n)$是嚴格單調(diào)遞增的勋功。類似的，若$m< n$蘊含$f(m) > f(n)$库说，則函數(shù)$f(n)$是嚴格單調(diào)遞減的狂鞋。

向上取整和向下取整

對于任意實數(shù)$x$，我們用$\lfloor x \rfloor$表示$x$的向下取整潜的，并用$\lceil x \rceil$表示$x$的向上取整骚揍。

對所有實數(shù)：
$$x - 1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x + 1$$
對任意整數(shù)n，
$$\lceil n / 2 \rceil + \lfloor n /2 \rfloor = n$$
對任意實數(shù)$x \geq 0$和整數(shù)$a,b >0$夏块，
$$\lceil \frac {\lceil x / a \rceil }疏咐 \rceil = \lceil \frac { x }{ab} \rceil$$
$$\lfloor \frac {\lfloor x / a \rfloor } \rfloor = \lfloor \frac { x }{ab} \rfloor $$
$$\lceil a / b \rceil \leq \frac {a + (b - 1)} 脐供$$
$$\lfloor a / b \rfloor \geq \frac {a - (b - 1)} $$
向下取整函數(shù)$f(x) = \lfloor x \rfloor$是單調(diào)遞增的借跪，向上取整函數(shù)$f(x) = \lceil x \rceil$也是單調(diào)遞增的政己。

模運算

對任意整數(shù)$a$和任意正整數(shù)$n$，$a\ mod \ n$的值就是商$a / n$的余數(shù)。
$$ a\ mod \ n = a - n \lfloor a / n \rfloor$$
結果有：
$$0 \leq a \ mod \ n < n$$

多項式

給定一個非負整數(shù)$d$歇由，n的d次多項式為具有以下形式的一個函數(shù)$p(n)$：
$$p(n) = \sum_{i = 0}^d a_i n^i$$

其中常量$a_1, a_2, \cdots, a_n$是多項式的系數(shù)且$a_d \neq 0$卵牍。一個多項式漸近正的當且僅當$a_d > 0$。對于一個$d$次漸近正的多項式$p(n)$沦泌，有$p(n) = \Theta(n^d)$糊昙。對任意實常數(shù)$a \geq 0$，函數(shù)$n^a$單調(diào)遞增谢谦，對任意實常量$a \leq 0$释牺，函數(shù)$n^a$單調(diào)遞減。若對某個常量$k$回挽，有$f(n) = O(n^k)$没咙，則稱函數(shù)$f(n)$是多項式有界的。

多項式

對所有實數(shù)$a > 0$千劈、$m$和$n$祭刚，我們有以下恒等式：
$$a^0 = 1$$
$$a^1 = a$$
$$a^-1 = 1/a$$
$$(a^m)n = a^{mn}$$
$$(a^m)n = (aⁿ⁾m$$
$$a^m a^n = a^{m + n}$$
對所有$n$和$a \geq 1$，函數(shù)$a^{n$關于$n$單調(diào)遞增墙牌。方便時涡驮，我們假定$0}0 = 1$。
可以通過以下事實使多項式與指數(shù)的增長率相關聯(lián)喜滨。多所有使得$a > 0$的實常量$a$和$b$遮怜，有
$$\lim_{n \to +\infty} \frac{n^b}{an} = 0$$
據(jù)此可得
$$n^b = o(a^n)$$
因此，<mark>任意底大于1的指數(shù)函數(shù)比任意多項式函數(shù)增長得快鸿市。</mark>

使用$e$來表示自然對數(shù)函數(shù)的底$2.71823\cdots$锯梁，對所有實數(shù)$x$，我們有
$$e^x = 1 + x + \frac {x^2} {2!} + \frac {x^3} {3!} + \cdots = \sum_{i = 0}^{\infty} \frac {x^i} {i!}$$
對所有實數(shù)$x$焰情，我們有不等式
$$e^x \geq 1 + x $$
對所有的$x$陌凳，我們有：
$$\lim_{n \to \infty} {\left(1 + \frac {x} {n} \right)}^n = e^x$$

對數(shù)

我們使用下面的記號：
$$lg\ n = log_2\ n \quad {以2為底的對數(shù)}$$
$$ln\ n = log_e\ n \quad {自然對數(shù)}$$
$$lg^k \ n = (lg\ n)^k \quad {取冪}$$
$$lglg\ n = lg(lg\ n) \quad {復合}$$
如果常量$b > 1$，那么對于$n > 0$内舟，函數(shù)$log_b n$是嚴格遞增的合敦。

對于所有實數(shù)$a > 0,\ b > 0,\ c > 0$和$n$，有
$$a = b^{log_b a}$$
$$log_c(ab) = log_ ca +log_c b$$
$$log_b{a^n} = nlog_b a$$
$$log_b a = \frac {log_c a} {log_c b}$$
$$log_b (1/a) = -log_b a$$
$$log_b a = \frac {1} {log_a b}$$
$$a^{lob_b c} = c^{log_b a}$$
其中验游，在上面的每個等式中充岛，對數(shù)的底不為1。

從公式$log_b a = \frac {log_c a} {log_c b}$中可以看出耕蝉，對數(shù)的底從一個常量到另一個常量的更換僅使對數(shù)的值改變一個常量因子崔梗，所以當我們不關心這些常量因子時，例如在$O$記號中垒在，我們經(jīng)常使用“$lg\ n$”蒜魄。計算機科學家發(fā)現(xiàn)2是對數(shù)的最自然的底，因為非常多的算法和數(shù)據(jù)結構涉及把一個問題分解成兩部分。

若對某個常量$k$谈为，$f(n) = O(lg^k \ n)$旅挤，則稱函數(shù)$f(n)$是多對數(shù)有界的。

多項式與多對數(shù)的增長相互關聯(lián)：
$$\lim_{n \to \infty} \frac{n^b}{an} = 0 \implies \lim_{n \to \infty} \frac {lg^b \ n} {(2^a){lg\ n}} = \lim_{n \to \infty} \frac {lg^b \ n} {n^a} = 0$$
根據(jù)這個極限伞鲫，我們可以得到：對任意常量$a >0$粘茄，
$$lg^b\ n = o(n^a)$$
因此，<mark>任意正的多項式函數(shù)都比任意對數(shù)函數(shù)增長的快秕脓。</mark>

階乘

記號$n!$柒瓣，定義為對整數(shù)$n \geq 0$，有：
$$ f(n)= \begin{cases} 1 & \text {若 n = 0} \ n \cdot (n - 1)! & \text {若 n > 0} \end{cases} $$
因此撒会，$n! = 1 \cdot 2 \cdot 3 \cdots n$嘹朗。
階乘函數(shù)一個弱上界是$n! \leq n^n $，因為在階乘中诵肛，$n$項的每項最多為$n$屹培。斯特林(Stirling)近似公式
$$n! = \sqrt{2 \pi n}\left(\frac n e\right)^n\left( 1 + \Theta \left( \frac 1 n \right)\right)$$
給出了一個更緊確的上界和下界，其中$e$是自然對數(shù)的底怔檩。
$$n! = o(n^n)$$
$$n! = \omega (2^n)$$
$$lg(n!) = \Theta(nlgn)$$
對所有$n \geq 1$褪秀，下面的等式也成立：
$$n! = \sqrt{2 \pi n}\left( \frac n e\right)^n e^{\alpha_n}$$
其中：
$$\frac 1 {12n +1} < n_\alpha < \frac 1 {12n}$$

多重函數(shù)

我們使用記號$f^{(i)}n$來表示函數(shù)$f(n)$重復$i$次作用與處置n上。形式化地薛训，假設$f(n)$為實數(shù)集上的一個函數(shù)媒吗。對非負整數(shù)$i$，我們遞歸地定義
$$f(n) = \begin{cases} n & \text {若 i = 0} \ f(f^{(i - 1)}(n)) & \text{若 i > 0} \end{cases}$$

多重對數(shù)函數(shù)

我們使用記號$lg^* \ n$來表示多重對數(shù)函數(shù)乙埃，下面給出它的定義闸英。假設$lg^{(i)}n$定義如上，其中$f(n) = lg\ n$介袜。因為非正數(shù)的對數(shù)無定義甫何，所以只有在$lg^{(i - 1)} > 0$時，$lg^{(i)}n$才有定義遇伞。定義多重對數(shù)函數(shù)為
$$lg^* \ n = min{i \geq 0 : lg^{(i)} n \leq 1}$$
多重對數(shù)函數(shù)是一個增長非常慢的函數(shù)辙喂。
$$lg^* \ 2 = 1$$
$$lg^* \ 4 = 2$$
$$lg^* \ 16 = 3$$
$$lg^* \ 65536 = 4$$
$$lg^* \ 2^{65536} = 5$$

菲波那切數(shù)

使用下面的遞歸式來定義菲波那切數(shù)：
$$F_0 = 0$$
$$F_1 = 1$$
$$F_i = F_{i - 1} + F_{i - 2}$$
因此，菲波那切數(shù)都是前面兩個數(shù)之和鸠珠，產(chǎn)生的序列為
$$1, 2, 3, 5, 8, 13, 21, 34, 55, \cdots$$
菲波那切數(shù)與黃金分割率$\phi$以及共軛數(shù)$\hat{\phi}$有關巍耗，它們是下列方程的兩個根：
$$x^2 = x + 1$$
并由下面的公式給出：
$$\phi = \frac{1 + \sqrt 5} {2} = 1.61803\cdots$$
$$\hat{\phi} = \frac{1 - \sqrt 5} {2} = -0.61803\cdots$$
特別地，我們有
$$F_i = \frac{\phi ^ i - \hat{\phi}^i} {\sqrt 5}$$
可以使用數(shù)學歸納法來證明這個結論渐排。因為$|\hat{\phi}| < 1$炬太，所以有
$$\frac{\hat{\phi}^i} {\sqrt 5} < \frac {1}{\sqrt 5} < \frac{1}{2}$$
這蘊含著
$$F_i = \lfloor \frac{\phi^i} {\sqrt 5} + \frac {1}{2} \rfloor$$
這就是說第$i$個菲波那切數(shù)$F_i$等于$\phi^i / \sqrt 5$舍入到最近的整數(shù)。因此菲波那切數(shù)以指數(shù)形式增長飞盆。

線性查找問題

輸入： n個數(shù)的一個序列$A=\langle a_1, a_2, \cdots, a_n\rangle $和一個值$v$娄琉。
輸出：下標$i$使得$v=A[i]$或者當 $v$不在A中出現(xiàn)時次乓，$i$為特殊值-1吓歇。

LINEAR-SEARCH(A, v)
    for i = 1 to A.length
        if v == A[i]
            return i
    return -1

java實現(xiàn)：

public static int linearSearch(int[] srcArr, int val) {
    for (int i = 0; i < srcArr.length; i++) {
        if (srcArr[i] == val)
            return i;
    }
    return -1;
}

如果數(shù)組$A$已經(jīng)排好序孽水，就可以將該序列的中點與$v$進行比較根據(jù)比較的結果，原序列中有一半就可以不用再進一步的考慮了城看。二分查找算法重復這個過程女气，每次都將序列剩余部分的規(guī)模減半。
非遞歸方式：

BINARY-SEARCH(A, v)
    low = 1
    high = A.length
    while low <= high
        middle = (low + high) / 2
        if A[middle] < v
            low = middle + 1
        elseif A[middle] > v
            high = middle - 1
        else
            return middle
    return -1

java實現(xiàn)：

/**
 * 利用非遞歸形式的二分查找法在數(shù)組中尋找特定的值
 * @param srcArray 被搜索的整形數(shù)組
 * @param val 待查找的值
 * @return 若該值在數(shù)組中测柠，返回該值對應的數(shù)組索引炼鞠。否則返回-1
 */
public static int binarySearch(int[]srcArray, int val){
    //低位“指針”
    int low = 0;
    //高位“指針”
    int high = srcArray.length - 1;
    //如果low ≤ high則進行查找，
    // 因為無論數(shù)組元素為偶數(shù)個還是奇數(shù)個轰胁，當要查找的值不在數(shù)組中時最后一步查找情況是low和high重合谒主，此時middle=low=high，
    // 如果srcArray[middle]>val赃阀，執(zhí)行l(wèi)ow = middle + 1霎肯，此時low>high;
    //如果srcArray[middle]<val，執(zhí)行high = middle - 1;榛斯，此時low>high;
    while(low <= high){
        int middle = (low + high) >> 1;
        //當數(shù)組中間值小于待查找值观游，該值“可能”在數(shù)組右半側，并且索引middle處的值已經(jīng)判斷過驮俗，所以low=middle+1懂缕，
        //并且如果low=middle,在[srcArray[low], srcArray[high]]會陷入死循環(huán)
        if(srcArray[middle] < val){
            low = middle + 1;
        }else if(srcArray[middle] > val){
            high = middle - 1;
            //找到待查找值，返回該值對應數(shù)組索引
        }else{
            return middle;
        }
    }
    //當待查找值不在數(shù)組中時返回-1
    return -1;
}

遞歸方式：

BINARY-SEARCH(A, low, high, val)
    while low <= high
        middle = (low + high) / 2
        if A[middle] == val
            return middle
        elseif A[middle] < val
            return BINARY-SEARCH(A, middle + 1, high, val)
        else 
            return BINARY-SEARCH(A, low, middle - 1, val)
    return -1

java實現(xiàn)：

public static int binarySearch(int[]srcArray, int low, int high, int val){
   while (low <= high) {
       int middle = (low + high) >> 1;
       if (srcArray[middle] == val) {
           return middle;
       } else if (srcArray[middle] < val)
           return binarySearch(srcArray, middle + 1, high, val);
       else
           return binarySearch(srcArray, low, middle - 1, val);
   }
    return -1;
}

排序

輸入： n個數(shù)的一個序列$\langle a_1, a_2, \cdots, a_n \rangle$王凑。
輸出：$\langle a^\prime_1, a^\prime_1, \cdots, a^\prime_n \rangle$搪柑，滿足 $ a^\prime_1 \leq a^\prime_2 \leq \cdots \leq a^\prime_n \rangle$。

插入排序

對于少量元素的排序索烹，它是一個有效的算法工碾。

在排好序的牌中插入一張新牌

如圖所示，一副完整的牌就像一個數(shù)組A术荤，手中的牌是A[1..j - 1]已經(jīng)按從小到大排好倚喂，這時你從桌子上的牌堆A[j..A.length]中取出一張牌A[j]，你要做的就是將這張牌插入到手中的牌里瓣戚。手中原來有牌{2端圈， 4， 5子库， 10}舱权，從桌子上取出一張牌是7，和最大的牌10比仑嗅，7<10宴倍，10往后移一個位置张症，7和5比，7>5鸵贬，那么就將7插入剛才10空出的位置俗他，以此類推。

INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    //Insert A[j] into the sorted sequence A[1..j - 1].
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

java實現(xiàn)

/**
* 對一個整型數(shù)組按從小到大的順序排序
 * @param arr 待排序的數(shù)組
 */
public static void insertionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        //將當前值key與已排好部分arr[0..i-1]中的值挨個比較大小
        //如果key大于已排好數(shù)組中arr[j],則將arr[j]往后“移一位”阔逼，將當前位置騰出來兆衅，保存key或前面移過來的值
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        //①如果key不小于已排好數(shù)組最大值（即已排好部分最后一個值），將key放到arr[j + 1]即arr[i]
        //相當于將arr[i]拿出來比較一下嗜浮，發(fā)現(xiàn)arr[i]不小于已排好數(shù)組中最大值羡亩，再講arr[i]放回去；
        //②如果key小于已排好數(shù)組最大值危融，那么經(jīng)過while循環(huán)當前的arr[j]是第一個小于key的數(shù)畏铆，所以將
        //key放在arr[j + 1]已騰出來的位置，arr[j + 1..arr[i]]里面的元素已經(jīng)依次向右移動一個位置吉殃。
        arr[j + 1] = key;
    }
}

插入排序的：

• 最好運行時間是$\Theta(n)$
• 最壞運行時間是$\Theta(n^2)$（讀作“theta n 平方”）辞居。

事實上，元素A[1, j - 1]就是原來1到j - 1的元素寨腔，但是現(xiàn)在已按順序排列速侈。我們把A[1..j-1]的這些性質(zhì)形式地表示為一個循環(huán)不變式。
循環(huán)不變式主要用來幫助我們理解算法的正確性迫卢。關于循環(huán)不變式倚搬，我們必須證明三條性質(zhì)：

• 初始化：循環(huán)的第一次迭代之前，它為真乾蛤。
• 保持：如果循環(huán)的某次迭代之前它為真每界，那么下次迭代之前塔仍然為真。
• 終止：在循環(huán)終止時家卖，不變式為我們提供一個有用的性質(zhì)眨层，該性質(zhì)有助于證明算法是正確的。

歸并排序

歸并排序算法完全遵循分治模式上荡，直觀上其操作如下：

1. 分解：分解帶排序的n個元素的序列成各具n/2個元素的兩個子序列趴樱。
2. 解決：使用歸并排序遞歸地排序兩個子序列。
3. 合并：合并兩個已經(jīng)排序的子序列以產(chǎn)生已排序的答案捺疼。

MERGE-SORT(A, p, r)
    if p < r
        q = ?(p + r) / 2?
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q, r)
        MERGE(A, p, q, r)

MEARGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    i = 1
    j = 1
    for k = p to r
        if i != n1 and (j == n2 or L[i] ≤ R[j])
            A[k] = L[i]
            i = i + 1
        else 
            A[k] = R[j]
            j = j + 1

java實現(xiàn)

 /**
* 給定一個數(shù)組，起始位置永罚，終止位置啤呼，對數(shù)組[起始位置..終止位置]按從小到大排序
 * @param arr 待排序數(shù)組
 * @param p 排序起始位置
 * @param r 排序終止位置
 */
public static void mergeSort(int[] arr, int p, int r){
    if (p < r){
        //取中間位置卧秘，將數(shù)組分為左右兩部分
        int q = (p + r) / 2;
        //遞歸對左數(shù)組進行排序
        mergeSort(arr, p, q);
        //遞歸對右數(shù)組進行排序
        mergeSort(arr, q + 1, r);
        //調(diào)用方法merge將數(shù)組中arr[p..r]部分進行排序
        merge(arr, p, q, r);
    }
}

/**
 * 給定一個數(shù)組arr，給定三個索引參數(shù)官扣，p醇锚、q哼御、r坯临，滿足p≤q≤r赶促，將arr[p..r]分成兩個數(shù)組
 * arr[p..q]和arr[q+1..r]，再融合兩個數(shù)組的過程中對數(shù)組進行排序挟炬，融合后的數(shù)組即排好序的數(shù)組
 * @param arr 待排序的數(shù)組
 * @param p 待排序數(shù)組首位索引
 * @param q 待排序數(shù)組中間索引
 * @param r 待排序數(shù)組摸位索引
 */
public static void merge(int[] arr, int p, int q, int r){
    int lLen = q - p + 1;
    int rLen = r - q;
    //用于接收左半數(shù)組
    int[] lArr = new int[lLen];
    //用于接收右半數(shù)組
    int[] rArr = new int[rLen];
    //將arr[p..q]復制到lArr
    System.arraycopy(arr, p, lArr, 0, lLen);
    //將arr[q+1..r]復制到rArr
    System.arraycopy(arr, q + 1, rArr, 0, rLen);
    int i = 0, j = 0;
    for (int k = p; k <= r; k++) {
        //取lArr中的值首先需要滿足lArr數(shù)組索引沒有越界鸥滨，這個前提下有兩種情況，
        //①rLen索引已到rLen.length谤祖，即rLen中的值都被取出
        //②兩個數(shù)組中都有值婿滓，并且lArr[i] <= rArr[j]
        if (i != lLen && (j == rLen || lArr[i] <= rArr[j])){
            arr[k] = lArr[i];
            i++;
        } else {
            arr[k] = rArr[j];
            j++;
        }
    }
}

選擇排序

考慮排序存儲在數(shù)組A中的n個數(shù)：首先找出A中的最小元素并將其與A[1]中的元素進行交換。接著粥喜，找出A中次最小元素并將其與A[2]中的元素進行交換凸主。對A中的前n-1個元素按該方式繼續(xù)。

SELECTION-SORT
for i = 1 to A.length - 1
    for j = i to A.lenth
        if A[j] < A[i]
            //change position
            temp = A[i]
            A[i] = A[j]
            A[j] = temp

java實現(xiàn)：

public static void selectionSort(int[] arr) {
   for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i; j < arr.length; j++) {
            if (arr[j] < arr[i]) {
                //①a ^ a = 0额湘；②a ^ 0 = a卿吐；③a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c；
                arr[i] = arr[i] ^ arr[j];
                // arr[j] = arr[i] ^ arr[j] ^ arr[j] = arr[i]
                arr[j] = arr[i] ^ arr[j];
                // arr[i] = arr[i] ^ arr[j] ^ arr[j] = arr[j] ^ arr[i] ^ arr[i] = arr[j]
                arr[i] = arr[i] ^ arr[j];
            }
        }
    }
}

分治策略

分治法：將原問題分解為幾個規(guī)模較小但類似于原問題的子問題锋华，遞歸地求解這些子問題嗡官，然后再合并這些子問題的解來建立原問題的解。
分治模式在每層遞歸時都有三個步驟：

1. 分解原問題為若干子問題毯焕，這些子問題是原問題的規(guī)模較小的實例衍腥。
2. 解決這些子問題，遞歸地求解各個子問題纳猫。然而婆咸，若子問題的規(guī)模足夠小，則直接求解续担。
3. 合并這些子問題的解成原問題的解擅耽。

遞歸式：遞歸式與分治方法是緊密相關的，因為使用遞歸式可以很自然地刻畫分治算法的運行時間物遇。一個遞歸式(recurrence)就是一個等式或一個不等式乖仇。

本章介紹三種求解遞歸式的方法憾儒，即得出算法“$\Theta$”和“$O$”漸近界的方法。

• 代入法 我們猜測一個界乃沙，然后用數(shù)學歸納法證明這個界的正確性起趾。
• 遞歸樹法 將遞歸式轉換為一顆樹，其節(jié)點表示不同層次的遞歸調(diào)用產(chǎn)生的代價警儒。然后采用邊界和技術求解遞歸式训裆。
• 主方法 可求解如下面公式的遞歸式的界：
  $$T(n) = aT(n / b) + f(n)$$
  其中$a \geq 1,\ b > 1,\ f(n)$是一個給定的函數(shù)。這種形式的遞歸式很常見蜀铲，它刻畫了一個這樣的分治算法：生成$a$個子問題边琉，每個子問題的規(guī)模是原問題的$1 / b$，分解和合并共花費時間$f(n)$记劝。

最大子數(shù)組問題

有一整形數(shù)組$A$变姨，找出$A$中和為最大的非空連續(xù)子數(shù)組。我們稱這樣的連續(xù)子數(shù)組為最大連續(xù)子數(shù)組厌丑。
<center>

最大子數(shù)組

暴力求解

遍歷所有可能的數(shù)組組合定欧，找出其中和最大的。

FIND-MAXIMUM-SUBARRAY(A, low, high)
    sum = -∞
    for i = 1 to A.length
        tempSum = 0
        for j = i to A.length
            tempSum = tempSum + A[j]
            if tempSum > sum
                sum = tempSum
                max-left = i
                max-right = j
    return (max-left, max-right, left-sum + right-sum)

java實現(xiàn)

public static int[] findMaximumSubarray(int[] arr, int low, int high) {
    //假設arr[0]就是最大連續(xù)子數(shù)組
   int sum = arr[0];
   int maxLeft = 0;
   int maxRight = 0;
   for (int i = 0; i < arr.length; i++) {
       int tempSum = 0;
       for (int j = i; j < arr.length; j++) {
           tempSum += arr[j];
           if (tempSum > sum) {
               sum = tempSum;
               maxLeft = i;
               maxRight = j;
           }
       }
   }
   return new int[]{maxLeft, maxRight, sum};
}

分治方法

過程FIND-MAX-CORSSING-SUBARRAY接受數(shù)組$A$和下標$low$怒竿、$mid$砍鸠、$high$作為輸入，返回一個下標元祖規(guī)定跨越中點的最大子數(shù)組的邊界耕驰，并返回最大子數(shù)組中值的和爷辱。

FIND-MAXIMUM-SUBARRAY(A, low, high)
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-CORSSING-SUBARRAY(A, low, mid, high)
    if left-sum ≥ right-sum and left-sum ≥ cross-sum
        return (left-low, left-high, left-sum)
    elseif right-sum ≥ left-sum and right-sum ≥ cross-sum
        return (right-low, right-high, right-sum)
    else return (cross-low, cross-high, cross-sum)

FIND-MAX-CORSSING-SUBARRAY(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)

java實現(xiàn)：

/**
     * 該方法接收一個數(shù)組和low、high下標耍属，找出其范圍內(nèi)的最大子數(shù)組
     * @param arr 被查找的數(shù)組
     * @param low 低位下標
     * @param high 高位下標
     * @return 最大子數(shù)組的起始位置托嚣，終止位置、和
     */
    public static int[] findMaximumSubarray(int[] arr, int low, int high) {
        //遞歸觸底反彈厚骗，子數(shù)組只有一個元素示启，所以arr[low]本身就是最大子數(shù)組
        if (low == high)
            return new int[]{low, high, arr[low]};
        else {
            int mid = (low + high) / 2;
            int[] leftArr = findMaximumSubarray(arr, low, mid);
            int[] rightArr = findMaximumSubarray(arr, mid + 1, high);
            int[] crossingArr = findMaxCrossingSubarray(arr, low, mid, high);
            if (leftArr[2] >= rightArr[2] && leftArr[2] >= crossingArr[2])
                return leftArr;
            else if (rightArr[2] >= leftArr[2] && rightArr[2] >= crossingArr[2])
                return rightArr;
            else
                return crossingArr;
        }
    }

    /**
     * 該方法接收一個數(shù)組arr和下標low,mid,high為輸入，返回一個下標元組劃定跨越中點的最大子數(shù)組的邊界领舰，
     * 并返回最大子數(shù)組中值的和夫嗓。
     * @param arr 被查詢的數(shù)組
     * @param low 低位下標
     * @param mid 中間位置下標，最大子數(shù)組跨越該點
     * @param high 高位下標
     * @return 最大子數(shù)組的起始位置冲秽，終止位置舍咖，和
     */
    public static int[] findMaxCrossingSubarray(int[] arr, int low, int mid, int high) {
        int maxLeft = mid;
        int maxRight = mid + 1;
        int leftSum = arr[mid];
        int sum = 0;
        for (int i = mid; i >= low; i--) {
            sum += arr[i];
            if (sum > leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }
        int rightSum = arr[mid + 1];
        sum = 0;
        for (int i = mid + 1; i <= high; i++) {
            sum += arr[i];
            if (sum > rightSum) {
                rightSum = sum;
                maxRight = i;
            }
        }
        return new int[]{maxLeft, maxRight, leftSum + rightSum};
    }

如果子數(shù)組A[low..high]包含n個元素，則調(diào)用FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)花費$\Theta(n)$時間锉桑。
初始調(diào)用FIND-MAXIMUM-SUBARRAY(A, 1, A.length)會求出A[1..n]的最大子數(shù)組排霉。

線性非分治方法

從數(shù)組的左邊界開始，由左至右處理民轴，記錄到目前為止已經(jīng)處理過的最大子數(shù)組攻柠。若已知A[1..j]的最大子數(shù)組球订，基于如下性質(zhì)將擴展為A[1..j+1]的最大子數(shù)組：A[1..j+1]的最大子數(shù)組要么是A[1..j]的最大子數(shù)組，要么是某個子數(shù)組A[i..j+1](1 ≤ i ≤ j+1)瑰钮。在已知A[1..j]的最大子數(shù)組的情況下冒滩，可以在線性時間內(nèi)找出形如A[i..j+1]的最大子數(shù)組。
有問題浪谴，但還是先記錄下开睡，$\Theta(n^2)$

/**
 * 該方法接收一個數(shù)組和low、high下標苟耻，找出其范圍內(nèi)的最大子數(shù)組
 * @param arr 被查找的數(shù)組
 * @param low 低位下標
 * @param high 高位下標
 * @return 最大子數(shù)組的起始位置篇恒，終止位置、和
 */
public static int[] findMaximumSubarray(int[] arr, int low, int high) {
    int maxLeft = low;
    int maxRight = low;
    int sum = arr[low];
    int tempSum;
    for (int i = 0; i < arr.length - 1; i++) {
        tempSum = 0;
        for (int j = i + 1; j >= 0 ; j--) {
            tempSum += arr[j];
            if (tempSum > sum) {
                maxLeft = j;
                maxRight = i + 1;
                sum = tempSum;
            }
        }
    }
    return new int[]{maxLeft, maxRight, sum};
}

矩陣乘法的Strassen算法

若$A=(a_{ij})$和$B=(b_{ij})$是$n\times n$的方陣梁呈，則對$i, j = 1, 2, \cdots, n$婚度，定義乘積$C = A \cdot B$中的元素$c_{ij}$為：
$$c_{ij} = \sum_{k = 1}^{n} a_{ik} \cdot b_{kj}$$
我們需要計算$n^2$個矩陣元素，每個元素是$n$個值得和官卡。根據(jù)定義下面過程接收$n \times n$矩陣$A$和$B$，返回它們的乘積——$n \times n$矩陣$C$醋虏。假設矩陣都有一個屬性$rows$寻咒，代表該矩陣的行數(shù)。

SQUARE-MATRIX-MULTIPLAY(A, B)
    n = A.rows
    for i = 1 to n
        cij = 0
        for j = 1 to n
            for k = 1 to n
                cij = cij + aik * bkj
    return C

由于三重for循環(huán)的每一重都恰好執(zhí)行n步颈嚼，而第三重的加法需要常量時間毛秘，因此過程SQUARE-MATRIX-MAULPLAY花費$\Theta(n^3)$時間。

java模擬
模擬矩陣的類阻课，用二維數(shù)組存儲值叫挟，重寫了toString()方法：

public class Matrix {
    private int rows; //矩陣的行數(shù)
    private int cols; //矩陣的列數(shù)
    private double[][] matrixArray; //代表矩陣的二維數(shù)組
    
    public Matrix(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        matrixArray = new double[rows][cols];
    }
    
    public Matrix(double[][] matrixArray) {
        rows = matrixArray.length;
        cols = matrixArray[0].length;
        this.matrixArray = matrixArray;
    }
    
    public int getRows() {
        return rows;
    }
    
    public void setRows(int rows) {
        this.rows = rows;
    }
    
    public int getCols() {
        return cols;
    }
    
    public void setCols(int cols) {
        this.cols = cols;
    }
    
    public double[][] getMatrixArray() {
        return matrixArray;
    }
    
    public void setMatrixArray(double[][] matrixArray) {
        this.matrixArray = matrixArray;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < matrixArray.length; i++) {
            for (int j = 0; j < matrixArray[i].length; j++) {
                sb.append(matrixArray[i][j] + "\t");
                if (j == matrixArray[i].length - 1)
                    sb.append("\n");
            }
        }
        return sb.toString();
    }
}

算法類，包含一個求兩個矩陣積的靜態(tài)方法：

public class Algorithms {
    /**
     * 接收兩個矩陣A, B返回兩者的乘積
     * @param matrixA 乘數(shù)A矩陣
     * @param matrixB 乘數(shù)B矩陣
     * @return 兩個矩陣的乘積
     */
    public static Matrix squareMatrixMultiply(Matrix matrixA, Matrix matrixB) {
        double[][] matrixAArray = matrixA.getMatrixArray();
        double[][] matrixBArray = matrixB.getMatrixArray();
        int rows = matrixA.getRows();
        int cols = matrixB.getCols();
        double sum = 0;
        double[][] matrixCArray = new double[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                sum = 0;
                for (int k = 0; k < cols; k++) {
                    sum = sum + matrixAArray[i][k] * matrixBArray[k][j];
                }
                matrixCArray[i][j] = sum;
            }
        }
        return new Matrix(matrixCArray);
    }
}

測試類：

public class TestAlgorithms {
    public static void main(String[] args) {
        double[][] matrixAArray = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        double[][] matrixBArray = {{12.3, 12, 56}, {34, 456, 234.2}, {93, 3434, 1314}};
        Matrix A = new Matrix(matrixAArray);
        Matrix B = new Matrix(matrixBArray);
        Matrix C = Algorithms.squareMatrixMultiply(A, B);
        System.out.println(C);
    }
}

輸出：
359.3 11226.0 4466.4
777.2 22932.0 9279.0
1195.1 34638.0 14091.6

假定將$A限煞、B$和$C$均分解為4個$n/2 \times n/2$的子矩陣：
$$ A = \begin{bmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \ \end{bmatrix}, \quad B = \begin{bmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \ \end{bmatrix}, \quad C = \begin{bmatrix} C_{11} & C_{12} \ C_{21} & C_{22} \ \end{bmatrix}, \quad $$
因此可以將公式$C = A \cdot B$改寫為：
$$\begin{bmatrix} C_{11} & C_{12} \ C_{21} & C_{22} \ \end{bmatrix} = \begin{bmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \ \end{bmatrix} \cdot $$\begin{bmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \ \end{bmatrix}
直接的遞歸分治算法：

SQUARE-MATRIX-MULPLAY-RECURSIVE(A, B)
    n = A.rows
    let C be a new n×n matrix
    if n == 1
        c11 = a11 · b11
    else
        C11 = SQUARE-MATRIX-MULPLAY-RECURSIVE(A11, B11)
            + SQUARE-MATRIX-MULPLAY-RECURSIVE(A12, B21)
        C12 = SQUARE-MATRIX-MULPLAY-RECURSIVE(A11, B12)
            + SQUARE-MATRIX-MULPLAY-RECURSIVE(A12, B22)
        C21 = SQUARE-MATRIX-MULPLAY-RECURSIVE(A21, B11)
            + SQUARE-MATRIX-MULPLAY-RECURSIVE(A22, B21)
        C22 = SQUARE-MATRIX-MULPLAY-RECURSIVE(A21, B12)
            + SQUARE-MATRIX-MULPLAY-RECURSIVE(A22, B22)
    return C

SQUARE-MATRIX-MULPLAY-RECURSIVE運行時間遞歸式：
$$T(n) = \begin{cases} \Theta(1) & \text {若 n = 1} \ 8T(n / 2) + \Theta(n^2) & \text{若 n > 1} \end{cases}$$
$T(n) = \Theta(n^3)$抹恳，說明簡單的分治算法并不優(yōu)于直接的SQUARE-MATRIX-MULPLAY算法。
java模擬
模擬矩陣的類繼續(xù)使用上一個方法中的Matrix署驻。
算法類：包含復制二維數(shù)組奋献、矩陣加法、合并矩陣旺上、矩陣乘法四個靜態(tài)方法

public class Algorithms {

    /**
     * 接收兩個矩陣A, B返回兩者的乘積
     * @param matrixA 乘數(shù)A矩陣
     * @param matrixB 乘數(shù)B矩陣
     * @return 兩個矩陣的乘積
     */
    public static Matrix squareMatrixMultiplyRecursive(Matrix matrixA, Matrix matrixB) {
        double[][] A = matrixA.getMatrixArray();
        double[][] B = matrixB.getMatrixArray();
        int rows = matrixA.getRows();
        double[][] C = new double[rows][rows];
        if (rows == 1) {
            C[0][0] = A[0][0] * B[0][0];
            return new Matrix(C);
        }
        else {
            int count = rows >> 1;
            double[][] A11Arr = arrayCopy(A, 0, 0, count);
            double[][] A12Arr = arrayCopy(A, 0, count, count);
            double[][] A21Arr = arrayCopy(A, count, 0, count);
            double[][] A22Arr = arrayCopy(A, count, count, count);
            double[][] B11Arr = arrayCopy(B, 0, 0, count);
            double[][] B12Arr = arrayCopy(B,0, count, count);
            double[][] B21Arr = arrayCopy(B, count, 0, count);
            double[][] B22Arr = arrayCopy(B, count, count, count);
            Matrix C11 = add(squareMatrixMultiplyRecursive(new Matrix(A11Arr), new Matrix(B11Arr)), squareMatrixMultiplyRecursive(new Matrix(A12Arr), new Matrix(B21Arr)));
            Matrix C12 = add(squareMatrixMultiplyRecursive(new Matrix(A11Arr), new Matrix(B12Arr)), squareMatrixMultiplyRecursive(new Matrix(A12Arr), new Matrix(B22Arr)));
            Matrix C21 = add(squareMatrixMultiplyRecursive(new Matrix(A21Arr), new Matrix(B11Arr)), squareMatrixMultiplyRecursive(new Matrix(A22Arr), new Matrix(B21Arr)));
            Matrix C22 = add(squareMatrixMultiplyRecursive(new Matrix(A21Arr), new Matrix(B12Arr)), squareMatrixMultiplyRecursive(new Matrix(A22Arr), new Matrix(B22Arr)));
            return combine(C11, C12, C21, C22);
        }
    }

    /**
     * 復制二維數(shù)組
     * @param srcArr 源數(shù)組
     * @param x 從二維數(shù)組中第幾個一維數(shù)組開始復制
     * @param y 從那個一維數(shù)組的第幾個元素開始復制
     * @param count 連續(xù)的作用到幾個一維數(shù)組瓶蚂，每個一維數(shù)組復制幾個值
     * @return 復制好的二維數(shù)組
     */
    public static double[][] arrayCopy(double[][] srcArr, int x, int y, int count) {
        double[][] destArr = new double[count][count];
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < count; j++) {
                destArr[i][j] = srcArr[x + i][y + j];
            }
        }
        return destArr;
    }

    /**
     * 求兩個矩陣的和
     * @param A 加數(shù)矩陣A
     * @param B 加數(shù)矩陣B
     * @return 兩個矩陣的和
     */
    public static Matrix add(Matrix A, Matrix B) {
        double[][] aArr = A.getMatrixArray();
        double[][] bArr = B.getMatrixArray();
        double[][] cArr = new double[aArr.length][bArr[0].length];
        for (int i = 0; i < aArr.length; i++) {
            for (int j = 0; j < aArr[i].length; j++) {
                cArr[i][j] = aArr[i][j] + bArr[i][j];
            }
        }
        return new Matrix(cArr);
    }

    /**
     * 將四個矩陣合并為一個矩陣
     * @param A11 子矩陣
     * @param A12 子矩陣
     * @param A21 子矩陣
     * @param A22 子矩陣
     * @return 合并后的矩陣
     */
    public static Matrix combine(Matrix A11, Matrix A12, Matrix A21, Matrix A22) {
        double[][] a11Arr = A11.getMatrixArray();
        double[][] a12Arr = A12.getMatrixArray();
        double[][] a21Arr = A21.getMatrixArray();
        double[][] a22Arr = A22.getMatrixArray();
        int rowsA = a11Arr.length;
        int colsA = a11Arr[0].length;
        int rowsB = a12Arr.length;
        int colsB = a12Arr[0].length;
        int rowsC = a21Arr.length;
        int colsC = a21Arr[0].length;
        int rowsD = a22Arr.length;
        int colsD = a22Arr[0].length;
        double[][] resultArr = new double[rowsA + rowsC][colsA + colsB];
        for (int i = 0; i < rowsA; i++) {
            for (int j = 0; j < colsA; j++) {
                resultArr[i][j] = a11Arr[i][j];
            }
        }
        for (int i = 0; i < rowsB; i++) {
            for (int j = 0; j < colsB; j++) {
                resultArr[i][colsA + j] = a12Arr[i][j];
            }
        }
        for (int i = 0; i < rowsC; i++) {
            for (int j = 0; j < colsC; j++) {
                resultArr[rowsA + i][j] = a21Arr[i][j];
            }
        }
        for (int i = 0; i < rowsD; i++) {
            for (int j = 0; j < colsD; j++) {
                resultArr[rowsA + i][colsA + j] = a22Arr[i][j];
            }
        }
        return new Matrix(resultArr);
    }

}

測試類：

public class TestAlgorithms {
    public static void main(String[] args) {
        double[][] matrixAArray = {{1, 2, 3, 3}, {4, 5, 6, 6}, {7, 8, 9, 9}, {1, 1, 1, 1}};
        double[][] matrixBArray = {{12.3, 12, 56, 1}, {34, 456, 234.2, 1}, {93, 3434, 1314, 1}, {1, 1, 1, 1}};
        Matrix A = new Matrix(matrixAArray);
        Matrix B = new Matrix(matrixBArray);
        Matrix C = Algorithms.squareMatrixMultiplyRecursive(A, B);
        System.out.println(C);
    }
}

輸出：
362.3 11229.0 4469.4 9.0
783.2 22938.0 9285.0 21.0
1204.1 34647.0 14100.6 33.0
140.3 3903.0 1605.2 4.0