• 24年秋的應(yīng)該是張老師最后一次用卷面考試，他說以后這節(jié)課的期末考試都是在OJ上刷題了
• 張老師上課還挺有意思的，上完之后能學(xué)會獨立地思考算法設(shè)計問題了。整節(jié)課都在強調(diào)規(guī)模壓縮這個概念，考試也是考個人對這些的理解，還挺好玩的哈哈

時間復(fù)雜度

$T(n)$ 表示算法在輸入規(guī)模為 $n$ 時的實際運行時間

在實際算法設(shè)計中常用以下三種：

• $O$ 即“小于等于”，描述$T(n)$的上界。
  
• $\Omega$ 即“大于等于”，描述$T(n)$的下界。
  
• $\Theta$ 表示“等于”，表示$T(n)$的上下界一致。
  $n^2,3n^2\in \Theta (n^2)$

主定理求遞推式的時間復(fù)雜度
$T(n)=aT(\frac{n}{b})+f(n)$

其中 $a$ 為歸約后的子問題個數(shù)，$n/b$ 為歸約后子問題的規(guī)模，$f(n)$為 split 和 merge 子問題的解的工作量。

直接上例題：

1. $T(n)=9T(\frac{n}{3})+n$
   即 $a=9，b=3，f(n)=n，n^{lo{g}_{b}a}=n^2$
   因為$f(n)=n<n^2$，即case 1，$T(n)=\Theta (n^2)$

2. $T(n)=T(\frac{2n}{3})+1$
   即$a=1，b=\frac{2}{3},f(n)=1,n^{lo{g}_{b}a}=1$
   因為 $f(n)==n^{lo{g}_{b}a}$，即case 2，此時k為0，即$T(n)=\Theta (logn)$

3. $T(n)=2T(\frac{n}{4})+n^2$
   即$a=2，b=4，f(n)=n^2,n^{lo{g}_{b}a}=n^{0.5}$
   因為 $f(n)>nlo{g}_{b}a$，所以是第三種，$T(n)=\Theta (n^2)$

排序

分-治-合并。

老師說的砍規(guī)模好像就包括了分和治。

砍規(guī)模干活多，則合并時候干活少。反之同理。
二分應(yīng)用于排序：對于quicksort和mergesort，快排在砍規(guī)模時先要讓兩邊各自大于或小于pivot，較麻煩;而合并不需要顯式操作，較簡單。歸并排序在砍規(guī)模時直接將數(shù)組分成兩半，較簡單;合并時要進(jìn)行兩個數(shù)組的排序和合并，較麻煩。

規(guī)模 n 推到規(guī)模 n-1應(yīng)用于排序：選擇排序、冒泡排序、插入排序，每次只減少一個問題數(shù)量，是較慢的。而這三個排序中，選擇排序和冒泡排序每次少一個未排序部分的最值元素，即砍規(guī)模時多干活。而插入排序每次少一個當(dāng)前游標(biāo)的元素(不一定是最值)，而需要在合并時將游標(biāo)元素在已排序部分插到合適的位置，即合并時多干活。

快排可能會退化，采用隨機策略可以避免最壞復(fù)雜度為$O(n^2)$

特殊線性排序不考。

建堆

按照樹的形態(tài)去砍規(guī)模。

砍規(guī)模干活多：比如大頂堆，先選一個最大的放在堆頂，然后遞歸地處理兩個子樹。相當(dāng)于規(guī)模直接砍半，無顯式合并。
$T(n)=2T(\frac{n}{2})+O(n)$，得$T(n)=\Theta (nlogn)$

砍規(guī)模干活少：從最后一個節(jié)點開始一下一下砍，直接找最后一個沒用的非葉節(jié)點即可。合并是將當(dāng)前子樹的根節(jié)點向下調(diào)整，耗時較長。$T(n)=2T(\frac{n}{2})+logn$，得$T(n)=\Theta (n)$

Insert：把元素插入到最后一項，再向上調(diào)整。(堆排序同理)

如果要動態(tài)挑最值，可以用優(yōu)先隊列輔助。

Select

找數(shù)組中第k小的元素。

類似快排的partition，數(shù)組二分后看topk在哪邊。

有種優(yōu)化策略，將數(shù)組先分為多組(每組中奇數(shù)個元素)，再在每組找個中位數(shù)，使用中位數(shù)的中位數(shù)作為pivot做partition。避免$O(n^2)$的最壞時間復(fù)雜度。

矩陣相乘的二分方法

不考

最大子數(shù)組

找和最大的非空連續(xù)子數(shù)組。

方法1：二分，將數(shù)組分為兩半，從左半部分、右半部分和跨中間這三部分的子數(shù)組中找個最大的?？缰虚g就是從中點往前面找個最大的后綴、往后邊找個最大的前綴，相加就是跨中間的最大子數(shù)組。

方法2：DP，每次減少一個問題的規(guī)模。用一個全局變量保存歷史最大子數(shù)組，并保存當(dāng)前位置之前的子數(shù)組情況。如果之前的子數(shù)組之和已經(jīng)為負(fù)數(shù)，則從當(dāng)前位置另起一個新子數(shù)組。否則擴展之前的子數(shù)組到當(dāng)前為止，即使當(dāng)前元素為負(fù)數(shù)，全局變量保存的仍是之前的全局最大子數(shù)組。

DP

優(yōu)化問題用到規(guī)模壓縮，即DP。

• 刻畫最優(yōu)子結(jié)構(gòu)。列遞推式/狀態(tài)轉(zhuǎn)移方程，能用中文解釋。
• 遞歸定義最優(yōu)解的值。
• 自下而上計算。原因：需要利用子問題，而多個父問題共享某些子問題，即子問題會被重復(fù)的求解。自下而上可以避免重復(fù)求解。如果改成自上而下，則需要使用備忘錄做記憶化。

有些問題不能用子問題求最優(yōu)解，比如最長簡單路徑問題，可能兩個最長簡單子路徑拼起來不是簡單路徑。

相關(guān)問題（計算題）：

1. 01背包

思路：窮舉是每個物品要么放入要么不放入，$O(2^n)$。如果當(dāng)前剩余容量為 k，在考慮第 i 個物品是否拿，拿不拿的兩種情況，都可以利用$dp[i?1][k]$這個子問題。由于不知道 k 是多少，每次都需要掃描一遍整個容量。

2. 最大子數(shù)組

上面寫了。

3. LCS最長公共子序列

思路：窮舉是$O(2^{m+n})$。如果已知當(dāng)前游標(biāo) $i$ 和 $j$ 前面的LCS，繼而可以得到當(dāng)前的LCS。即滿足最優(yōu)子結(jié)構(gòu)。$dp$數(shù)組起到備忘錄的作用。

設(shè) $dp[i][j]$ 表示序列 $X$ 的前 $i$個字符和序列 $Y$ 的前 $j$ 個字符的 LCS 長度。

m, n = len(X), len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):for j in range(1, n + 1):if X[i - 1] == Y[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

4. 矩陣鏈乘

對于矩陣數(shù)組$[A1,A2,A3]$的鏈乘最小代價，可以通過$[A1,A2]?[A3]$和$[A1]?[A2,A3]$的代價得到，利用了$[A1,A2]$和$[A2,A3]$這兩個子問題。擴展即可知道子問題就是在各個分割點分割之后的子數(shù)組，利用子問題的方式就是從子問題中選一個最值。滿足最優(yōu)子結(jié)構(gòu)。

會重復(fù)利用較短的子數(shù)組，所以自下而上，用個dp數(shù)組做備忘錄。

5. ALS裝配線調(diào)度

就是給了兩條裝配線的進(jìn)入耗時、出去耗時。然后兩條裝配線在功能上是相同的，有多個裝配站，兩條線上同一個下標(biāo)的裝配站是功能相同，但用時可能不同。所以有個切換操作，可以把物品從一條線搬到另一條線，試圖加速。所以要求一個物品完成裝配花費的最短時間。長的像最短路徑，其實因為方向是固定的，所以不是圖而是樹，問題稍微簡單一點。

dp方法見下圖。

貪心

如果可以直接知道用哪個子問題也能得到最優(yōu)解，不用比較各個子問題的結(jié)果，就可以貪心、即貪心$\in$DP。
相關(guān)問題如：

• 分?jǐn)?shù)背包：優(yōu)先選單價高的。

• 哈夫曼樹：權(quán)重越高的字符，編碼長度越短。權(quán)重越高，越會被后挑選，即越接近根節(jié)點。
  

• 活動選擇：多個活動有起止時間，只能選互不沖突的，使活動數(shù)量最大化。DP是在當(dāng)前活動處，找前面最后一個兼容本活動的活動，然后選或者不選，dp[i]是到前i個活動的最多兼容活動數(shù)。貪心策略是優(yōu)先選結(jié)束時間早的，為后續(xù)活動留下更多時間。

最短路徑

重點是確定通過計算次序。

之前的問題都是可以轉(zhuǎn)化為一棵樹，子問題向上擴展，最終得解。

而b->c、c->b都有可能，即c可以利用b之前的最短路徑、b也可以利用c之前的最短路徑。所以不能是一棵向上的樹。所以需要確定一個計算次序，即誰是子問題。

Dijkstra

在無負(fù)權(quán)環(huán)的時候，這個計算次序是有的。他是子問題找父問題，即找一個最近的節(jié)點。如果有負(fù)權(quán)環(huán)，則有些很遠(yuǎn)節(jié)點的距離反而越來越近，計算次序就出現(xiàn)問題了。通過計算次序理解為什么是dp。

Bellman-ford

允許負(fù)權(quán)環(huán)，所以沒有計算次序，所以迭代多輪來補償。單源。個人感覺就是Floyd的單源形式。

SPFA就是如果有些點被更新后，才加入隊列進(jìn)行后續(xù)的松弛更新。

如果第V次還能松弛，說明有負(fù)權(quán)環(huán)。

Floyd

多源。$dp[i][j][k]$，已知未使用 k 時，i 到 j 的最短路徑，看用 k 是否能繼續(xù)縮短。

時間復(fù)雜度

floyd是$O(V^3)$。

迪杰斯特拉是每次找一個最近的點，然后基于這個中轉(zhuǎn)點更新源點到中轉(zhuǎn)點的鄰點。所以對于鄰接矩陣的實現(xiàn)，是V的循環(huán)里套個找鄰點的V，$O(V^2)$
Bellman-ford是重復(fù)V-1次，然后松弛所有邊，所以是$O(V?E)$

搜索

無法用規(guī)模壓縮，只能蠻力窮舉。

設(shè)定邊界減少不必要的搜索。

限界函數(shù)：殺死更多的節(jié)點、效率。

NP問題

P可以在多項式時間內(nèi)求解，NP只能在多項式問題內(nèi)驗證解。

NPC(理論上可解，窮舉)：circuit-sat(電路可滿足)、TSP(旅行商)、3-color三色(平面圖染三色，使得相鄰區(qū)域顏色不同)、哈密爾頓路徑。

不可判定：Hilbert’s Tenth Problem(希爾伯特第十問題)、Halting Problen(停機問題)、Post Correspondence Problem(PCP)、Program Equivalence Problem(程序等價性問題)、Optimal Data Compression Problem(最優(yōu)數(shù)據(jù)壓縮問題)、Virus Identification Problem(病毒識別問題)、多元多項式整數(shù)根（費馬大定理）、普斯特對應(yīng)問題