麻省理工學(xué)院公開課：算法導(dǎo)論台腥。B站地址，網(wǎng)易公開課也有對應(yīng)的資源绒北。
https://www.bilibili.com/video/av1149902/?p=3

這節(jié)課主要講解分治法解決各種問題的思路黎侈。
所謂分治法，大概分三個步驟：
1闷游、分：把問題劃分成若干個子問題
2蜓竹、治：遞歸地解決每一個子問題
3箕母、合并：把子問題的解，合并成整個大問題的解

歸并排序

之前兩節(jié)課程都提到的歸并排序（這里就不詳細寫了）
1俱济、把待排序的數(shù)組一分為二
2嘶是、分開處理每一部分
3、合并蛛碌，時間復(fù)雜度為Θ(n)

每一個符合分治策略的算法聂喇，幾乎都有相似形式的遞歸出現(xiàn)，如上節(jié)課學(xué)習(xí)的主定理（主方法）

練習(xí)——主定理應(yīng)用到歸并排序中
歸并排序的遞歸表達式：T(n) = 2T(n/2) + Θ(n)
2T(n/2)中蔚携，第一個2表示子問題的數(shù)目希太，第二個2表示子問題的規(guī)模，Θ(n)表示合并需要的計算量酝蜒。
根據(jù)上一節(jié)課的主定理可知：
n^log_ba = n^log₂2 = n
f(n) = n
即為第二種情況誊辉，整理的時間復(fù)雜度為T(n) = Θ(nlgn)

二分查找算法（Binary Search）

在一個已排序的數(shù)組中尋找元素x
1、分：把x和數(shù)組的中間元素進行比較
2亡脑、治：由上一步找到對應(yīng)的子數(shù)組堕澄，然后重復(fù)1
3、合并（這里只是找到x即可霉咨，不需要合并蛙紫，所以之類這一步可以省略）
這個問題的遞歸表達式：T(n) = T(n/2) + Θ(1)
根據(jù)上一節(jié)課的主定理可知：
n^log_ba = n^log₂1 = n⁰ = 1
f(n) = 1
即為第二種情況，整體時間復(fù)雜度為 Θ(lgn)

乘方問題

存在某數(shù)x途戒，正整數(shù)n坑傅，求xⁿ
思路：
① 簡單粗暴地直接算的話，就是把x連乘n次喷斋，然后得出結(jié)果唁毒。時間復(fù)雜度明顯為Θ(n)
② 上面的思路說說而已啦啦，用分治法看下

1. 分：根據(jù)n為偶數(shù)/奇數(shù)星爪，求不同的結(jié)果
   n為偶數(shù)時浆西，xⁿ = x^n/2·x^n/2
   n為奇數(shù)時，xⁿ = x^(n-1)/2·x^(n-1)/2·x
2. 治：分別求出每一子項的結(jié)果
3. 合并：將每一子項的結(jié)果再合并起來移必，時間復(fù)雜度為Θ(1)

遞歸表達式為T(n) = T(n/2) + Θ(1)

之前在LeetCode刷過相同的題室谚，題號50。這里要考慮的情況比較多崔泵，如n為負數(shù)的情況秒赤。下面是自己寫的JavaScript版的答案：【挺久之前寫的題了，當時想著不一定要遞歸分解到最后x²的情況再合并憎瘸，所以寫個getZhishu()來獲取最優(yōu)的分解入篮，提交通過』细剩】

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    // 要處理n為負數(shù)的情況
    var result = 1;
    var N = Math.abs(n);

    if(x===1){
        return 1;
    }
    // 把N拆解一下潮售，
    var arr = getZhishu(N);
    var tmp = x;
    for(var i=0;i<arr.length;i++){
        // 要記得重置result的值
        result = 1;
        for(var j=1;j<=arr[i];j++){
            result *= tmp;
        }
        tmp = result;
    }
    return n>=0 ? result : 1/result;
};
// 把sum分解為多個數(shù)的乘積痊项，要求所有元素的和為最小。
var getZhishu = function(num){
    var result = [];
    var _num = num;
    var middle = parseInt(_num/2, 10);
    for(var i=2;i<=middle;){
        if(_num%i === 0){
            // 如果可以除盡
            _num /= i;
            middle = parseInt(_num/2, 10);
            result.push(i);
            i = 2;
        }else{
            i++;
        }
    }
    // 把最后一個加進去
    result.push(_num);
    return result;
};

嘗試用遞歸的方法處理一下酥诽，但是在一些邊緣情況（如：x=0.00001鞍泉，n=2147483647）的時候會超時，應(yīng)該是陷入遞歸里面出不來肮帐，需要要做一些特殊處理咖驮。

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    // 要處理n為負數(shù)的情況
    var result = 1;
    var N = Math.abs(n);

    if(x===1){
        return 1;
    }

    result = getNum(x, N);
    
    return n>=0 ? result : 1/result;
};
var getNum = function(x, n){
    if(n===0){
        return 1;
    }
    if(n===1){
        return x;
    }
    if(n&1){
        return getNum(x, parseInt(n/2)) * getNum(x, parseInt(n/2)) * x;
    }else{
        return getNum(x, n/2) * getNum(x, n/2);
    }
}

斐波那契數(shù)

斐波那契數(shù)的定義為
F₀ = 0，n=0
F₁ = 1训枢，n=1
F_n = F_n-1 + F_n-2托修，n≥2

求解斐波那契數(shù)有兩種算法。
① 遞歸算法恒界，一層一層往下遞歸計算睦刃，時間復(fù)雜度為指數(shù)級

② 自下而上遞歸算法，從0十酣，1開始向上遞歸解決涩拙，時間復(fù)雜度為Θ(n)，但這還不是最優(yōu)解婆誓〕曰罚【下面LeetCode的70題是同樣的思路也颤⊙蠡茫】

之前在LeetCode刷過相同的題，題號70和746翅娶。均為JavaScript版本文留。

// 第70題，爬樓梯
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n===1 || n===2){
        return n;
    }
    var a = 1;
    var b = 2;
    for(var i=3;i<n;i++){
        var tmp = a+b;
        a = b;
        b = tmp;
    }
    return a+b;
};

③ 可以運用上面求乘方（樸素平方遞歸式）的方法來求
時間復(fù)雜度為lgn竭沫，但因為各種原因這個方法在現(xiàn)實中的機器上是不能實現(xiàn)的燥翅。但是可以運用斐波那契數(shù)的特性，用另一種方式來實現(xiàn)平方遞歸蜕提。
即
用矩陣來計算森书，時間復(fù)雜度為lgn（同前面的乘方問題，只是x換成了矩陣）谎势，因為矩陣相乘的時間復(fù)雜度為常數(shù)凛膏，所以整體時間復(fù)雜度為Θ(lgn)。

這是定理

使用歸納法來證明上面的定理：
首先脏榆，基礎(chǔ)情況

進一步歸納

也就是

矩陣乘法

A和B都是n x n的矩陣猖毫，A = [a_ij]，B = [b_ij]须喂，其中1 ≤ i,j ≤ n吁断。兩者的乘積C = [c_ij] = A*B
C中的某一項的值如下：

求取矩陣C的算法趁蕊，時間復(fù)雜度為Θ(n³)。因為C一共有n²項需要求取仔役，而且求取每一項c_ij的時間復(fù)雜度掷伙，根據(jù)上面的公式可得，為Θ(n)又兵，所以總的時間復(fù)雜度為Θ(n³)炎咖。

代碼如下：

for(var i=0;i<n;i++){
    for(var j=0;j<n;j++){
        c[i][j] = 0;
        for(var k=0;k<n;k++){
            c[i][j] += a[i][k]*b[k][j];
        }
    }
}

現(xiàn)在要對矩陣乘法進行優(yōu)化。

斯特拉森算法（Strassen's Algorithm）
首先寒波，前面用分治法的場景大多是把規(guī)模為n的問題分解為2個規(guī)模為n/2的問題乘盼，然后再分開求解合并。但是這里俄烁，矩陣的規(guī)模是n²绸栅。
用矩陣分塊來處理，第一步先把矩陣分解成2x2塊規(guī)模為(n/2)*(n/2)的子矩陣页屠。
對ABC三個矩陣都進行分割粹胯，如圖：

C = A * B

先不關(guān)心r、s辰企、t风纠、r這些模塊內(nèi)部詳細的結(jié)果。把它簡單化為一個2*2的矩陣
其中根據(jù)矩陣的乘法牢贸，可得：

r = ae + bg
s = af + bh
t = ce + dg
u = cf+dh

遞歸表達式描述為 T(n) = 8T(n/2) + Θ(n²)
Θ(n²) 為以上矩陣求和（如ae+bg）的時間復(fù)雜度竹观。

根據(jù)上節(jié)課的主定理，n^log_ba = n^log₂8 = n³潜索，f(n) = n²臭增，歲時間復(fù)雜度為 T(n) = Θ(n³)。

下面用斯特拉森算法來講竹习。斯特拉森算法的原理在于減少乘法的次數(shù)誊抛，把8T(n/2) 變?yōu)?T(n/2)。
兩個2x2的矩陣在求乘積的時候整陌，一共需要進行8次乘法拗窃。

P₁ = a(f-h)
P₂ = (a+b)h
P₃ = (c+d)e
P₄ = d(g-e)
P₅ = (a+d)(e+h)
P₆ = (b-d)(g+h)
P₇ = (a-c)(e+f)

r = P₅ + P₄ - P₂ + P₆
s = P₁ + P₂
t = P₃ + P₄
u = P₅ + P₁ - P₃ - P₇

其中，驗證一下u的值是否正確
u = P₅ + P₁ - P₃ - P₇
.. = (ae+ah+de+dh) + (af-ah) - (ce+de) - (ae+af-ce-cf)
.. = dh + cf

同上面的計算結(jié)果一致泌辫，這里省略r s t的證明随夸。
用分治法來看一下這個算法：

1. 分：
   要計算出所有的P_i內(nèi)各種加減法的值，需要消耗n²的時間甥郑。
2. 治
   遞歸求出所有P_i的值逃魄，共進行7個乘法。
3. 合并
   分別求出r s t u澜搅，都是加減法伍俘，時間n²邪锌。

所以遞歸表達式為T(n) = 7T(n/2) + Θ(n²)，求得時間復(fù)雜度為Θ(n^lg7)癌瘾，即Θ(n^2.81)觅丰。

VLSI（超大規(guī)模集成電路）問題

問題可簡化為：有個完全二叉樹，共n個葉節(jié)點妨退，要在網(wǎng)格上占據(jù)最小的空間妇萄，應(yīng)該如何進行布局。
這里講解了兩個方法
① 樸素算法
② 復(fù)雜度為Θ(n)的算法

樸素算法

在線畫電路圖比較麻煩咬荷，所以上傳手動圖冠句。
這棵樹的高度H(n) = lgn，寬度W(n) = n幸乒，所以其面積Area = Θ(nlgn)懦底。

復(fù)雜度為Θ(n)的算法
因為Area = H * W，所以要使Area = Θ(n)罕扎，可以讓H和W都分別為根號n聚唐。
那么根據(jù)上節(jié)課的主方法，逆推一下腔召，可得b = a²杆查，假設(shè)a=2，那么其遞歸表達式應(yīng)為T(n) = 2T(n/4) + O(n^(1/2)-ε)臀蛛。畫出其遞歸樹如下：