麻省理工學院公開課：算法導論。B站地址，網(wǎng)易公開課也有對應的資源。
https://www.bilibili.com/video/av1149902/?p=2

第二集的內(nèi)容比較多（雖然視頻比第一集短了大概10分鐘），講的都是數(shù)學的內(nèi)容，不涉及算法。主要內(nèi)容是漸近符號、遞歸及其解法。內(nèi)容比較難，而且都是數(shù)學相關的，從畢業(yè)之后就不怎么接觸了，所以理解起來有難度。

漸近符號

基本的漸近符號：
O 表示上界，即小于等于 ≤
Ω 表示下界，即大于等于 ≥
Θ 表示漸近等于 =（上一集也有使用這個符號）

還有幾個嚴格符號：
o 表示小于 <
ω 表示大于 >

漸近符號O

主要詳細講解了漸近符號O
對于f(n) = O(g(n))，表示存在適當?shù)某?shù)c>0,n₀>0，使得f(n) ≤ c·g(n)，對于所有的n≥n₀

f(n)可以說是屬于g(n)構成的函數(shù)集，可以定義O(g(n))為一個函數(shù)集
O(g(n)) = { f(n)：存在c>0、n₀>0，使得0≤f(n)≤cg(n)，其中n≥n₀ }

嚴格意義上來講，f(n) = O(g(n))中的等號=是不對稱的，即不能從右邊推算到左邊。這里表達的意思是屬于某個集合，即相當于f(n) ∈ O(g(n))

有一些關于O符號的精妙用法，把它當作宏來用，
例子：f(n) = n³ + O(n²)
表示f(n)主要是n³，但是還有個低階項O(n²)。即存在某函數(shù)h(n)=O(n²)，使得f(n) = n³ + h(n)。O(n²)是一個誤差項

例子：n² + O(n) = O(n²)
表示對所有f(n)∈O(n)，存在h(n)∈O(n²)，使得n²+f(n)=h(n)

漸近符號Ω

f(n) = Ω(g(n)) 這里比較簡單帶過，Ω的集合版定義為：
Ω(g(n)) = { f(n)：存在c>0、n₀>0，使得0≤cg(n)≤f(n)，其中n≥n₀ }

漸近符號Θ

Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

解遞歸式

解遞歸式?jīng)]有通用的方法（沒有萬金油），但是有三種主要的方法：代換法、遞歸樹法、主方法。

代換法

代換法和解積分類似，主要有三個步驟：

1. 猜答案，不需要非常精確
2. 驗證
3. 找出常數(shù)系數(shù)，使問題成立

注：代換法的驗證是使用數(shù)學歸納法，在這一步不能使用O符號。

一個錯誤的證明：
要證明n=O(1)【顯然是不成立的，不然所有算法都是常數(shù)復雜度了】
因為
1 = O(1)
...（逐步歸納）
n-1 = O(1)
所以n = (n-1)+1 = O(1) + O(1) = O(1)

上面的證明是錯誤的，不能在歸納中使用O，因為這里的常數(shù)是變化的。如果是有窮數(shù)量的常數(shù)加倍，沒太大問題，這依然是一個常數(shù)。但如果是2^k次的這種加倍就有問題了，常數(shù)是依賴于n變化的。在歸納過程中，要保證常數(shù)系數(shù)是不變的。

練習一

T(n) = 4T(n/2) + n
T(1) = Θ(1)

1. 猜測①：T(n) = O(n³)
2. 驗證：T(k) ≤ c(k³)，其中k<n

驗證過程如下：
T(n) = 4T(n/2)+n
....... ≤ 4c(n/2)³+n
....... = (1/2)cn³+n
....... = cn³-[(1/2)cn³-n]
其中，cn³為理想情況，余項=[(1/2)cn³-n]
T(n) ≤ cn³, if 余項=[(1/2)cn³-n]≥0
這里的c是一個常數(shù)系數(shù)，可以設定任何想要的值。比如設置c=2，猜測成立。

1. 猜測②：T(n)=O(n²)
2. 驗證：T(k) ≤ c(k²)，其中k<n

驗證過程如下：
T(n) = 4T(n/2)+n
....... ≤ 4c(n/2)²+n
....... = cn²+n
....... = cn²-(-n)
其中，cn²為理想情況，余項=-n
T(n) ≤ cn², if 余項=-n ≥ 0
因為n≥1，所以顯然不成立。

1. 猜測③：T(n) = O(c₁n²-c₂n)
2. 驗證：T(k) ≤ c₁k²-c₂k，其中k<n

驗證過程如下：
T(n) = 4T(n/2)+n
....... ≤ 4[c₁(n/2)²-c₂(n/2)]+n
....... = c₁n² - 2c₂n + n
....... = c₁n² - c₂n - (c₂n-n)

其中，c₁n²為理想情況，余項=c₂n-n
so，T(n) ≤ c₁n²-c₂n，if 余項=c₂n-n ≥ 0，即c₂≥1。
當n=1，T(1) ≤ c₁ - c₂，又因為T(1) = Θ(1)，故c₁>c₂。

一般大家都比較關心上界，所以只求O，不過偶爾也會求一下下界Ω。

遞歸樹法

在上一集講歸并排序的時候，講了一點遞歸樹法。這節(jié)課找了個稍微復雜點的例子。

練習二

T(n) = T(n/4) + T(n/2) + n²
....... = n² + T(n/4) +T(n/2)
....... = n² + (n/4)² + T(n/16) + T(n/8) + (n/2)² + T(n/8) + T(n/4)
....... = n² + (n/4)² + (n/2)² + [(n/16)²] + [(n/8)²] + [(n/8)²] + [(n/4)²]
....... = ...

注：為了簡潔書寫，表示[(n/8)²]表示T(n/8)的展開形式

用腦圖來表示遞歸樹
第一次展開：T(n) = T(n/4) + T(n/2) + n²，如下圖：

T(n) = T(n/4) + T(n/2) + n^2

第二次展開：T(n) = n² + (n/4)² + T(n/16) + T(n/8) + (n/2)² + T(n/8) + T(n/4)，如下圖：

T(n) = n^2 + (n/4)^2 + T(n/16) + T(n/8) + (n/2)^2 + T(n/8) + T(n/4)

繼續(xù)展開：

...

觀察得到，算法的初始規(guī)模為T(n)，每次遞歸分解為一個T(n/4)和T(n/2)，每次都會比上一級減少1/4的n，所以可推斷最后的葉節(jié)點數(shù)量 < n

一直遞歸到T(1)，即常數(shù)。觀察可得，遞歸樹每層n²的系數(shù)是一個等比級數(shù)，如第一層為1，第二層為5/16，第三層為25/256......
可得n²的系數(shù)總和=1 + 5/16 + 5²/16² + ... + 5^k/16^k ≤ 2

也就是T(n) ≤ 2n² +n = O(n²)

主方法

主方法是遞歸樹法的一個應用，但是比遞歸樹法更精確。但只能應用到特定的遞歸式上。
特定的遞歸式：
T(n) = aT(n/b)+f(n)，其中a≥1，b>1，f(n)漸近趨正。
對于規(guī)模為n的算法，每次遞歸可以轉化為a個規(guī)模為n/b的算法，以及一個非遞歸的代價f(n)。

漸近趨正：對于足夠大的n，f(n)是正的。即存在n0，當n≥n0，f(n)>0。

主方法有個簡單的思路：比較非遞歸函數(shù)f(n)和函數(shù)n^log_ba（表示遞歸樹葉節(jié)點的數(shù)量）的大小，比較的結果有三種情況：小于，等于，大于。

1. 情況一：小于
   對于第一種情況，f(n) < n^log_ba。
   即：f(n) = O(n^{log_ba - ε})，ε>0
   ==> T(n) = Θ(n^log_ba)，即由n^log_ba作為主導，忽略f(n)。

2. 情況二：等于
   第二種情況，f(n) = n^log_ba
   注意：這里的等于不是完全等于，而是基本等于。
   即：f(n) = Θ(n^log_ba · lg^kn)，k≥0
   ==> T(n) = Θ(n^log_ba · lg^k+1n)，即f(n)·h，h=lgn。

3. 情況三：大于
   第三種情況，f(n) > n^log_ba
   即：f(n) = Ω(n^{log_ba + ε})，ε>0
   還需要考慮f(n)是如何增長的，需要確保在遞歸的過程中，f是不斷減小的，否則可能得到無限大的值。。
   即要求【下一層的總代價af(n/b)】 ≤ 【小于當前層的代價(1-ε')f(n)】 ，ε' > 0，(1-ε')表示嚴格<1
   ==> T(n) = Θ(f(n))，即由f(n)作主導，忽略n^log_ba。

練習三

T(n) = 4T(n/2)+n
代入以上的公式【T(n)=aT(n/b)+f(n)】可得：a=4,b=2,f(n)=n
計算可得n^log_ba = n²
接下來比較 f(n)=n 和 n^log_ba=n²
因為n ≤ n²，所以符合第一種情況，故T(n) = Θ(n²)

練習四

T(n) = 4T(n/2)+n²
代入以上的公式【T(n)=aT(n/b)+f(n)】可得：a=4,b=2,f(n)=n²
計算可得n^log_ba = n²
接下來比較 f(n)=n² 和 n^log_ba=n²
因為n² == n²，所以符合第二種情況，故T(n) = Θ(n²lg^k+1n)
即T(n) = Θ(n²lgn)，設定k=0

練習五

T(n) = 4T(n/2)+n³
省略一下推算，符合第三種情況
即T(n) = Θ(n³)

主方法的證明

下面用遞歸樹法證明主方法是成立的
T(n) = aT(n/b) + f(n)
...... = f(n) + f(n/b) + f(n/b) + ... + f(n/b) -------------------- a個f(n/b)
...... = f(n/b²) + f(n/b²) + ... + f(n/b²)----------------a²個f(n/b)
...... = 常數(shù) ----------Θ(1)

用腦圖來表示遞歸樹
第一次展開：T(n) = aT(n/b) + f(n)，如下圖：

T(n) = aT(n/b) + f(n)

第二次展開：T(n) = f(n) + af(n/b) + a²T(n/b²)，如下圖：

T(n) = f(n) + af(n/b) + a^2T(n/b^2)

繼續(xù)展開如圖：

...

求取最后葉節(jié)點的數(shù)量leaves，以及遞歸樹的高度height。

• 高度 height = log_bn【這個比較好求，等下在后面補充一下】
• 葉節(jié)點leaves = a^height = a^log_bn
  根據(jù)對數(shù)的性質：a^log_bn = n^log_ba，故leaves = n^log_ba
  對于最后Θ(1)的葉節(jié)點，共n^log_ba片，時間復雜度為Θ(n^log_ba)

接下來比較遞歸樹最底層的n^log_ba和最頂層的f(n)。
對于第三種情況，f(n)>n^log_ba，遞歸的代價a^kf(n/b^k) 逐漸降低，即成本呈幾何級數(shù)降低，由最頂層的f(n)占主導，故Θ(f(n))。
對于第一種情況，f(n)<n^log_ba，遞歸成本呈幾何級數(shù)增長，時間復雜度由最底層的成本n^log_ba占主導，故Θ(n^log_ba)。
對于第二種情況，f(n)=n^log_ba，每一層的成本都漸近地相等，故時間復雜度為Θ(f(n)·h) = Θ(f(n)·log_bn) = Θ(f(n)·lgn)。

如何求得遞歸樹的高度為 log_bn?
n
n/b
n/b²
n/b³
...
n/b^k ------- 1
遞歸樹的高度為n --> 1的高度，即n --> n/b^k的高度。由上面的圖可得高度為k，而n/b^k = 1，即n=b^k，即k=log_bn。