【演算法】筆記一

動態規劃

1. 生產線問題，到達每一關最短的時間，可以由上一關的最短時間加上多的時間比較而知，由此遞迴需時O(2^n)。使用動態規劃只需 O(n)。
2. 具有以下兩性質者可以利用動態規劃：
1. optimal substructure：可以使用遞迴。
2. Overlapping Subproblems：遞迴時會重複遇到同樣的問題。
3. m*n 矩陣和 n*o 矩陣相乘需要運算 O(mno) 次，得到 m*o 矩陣。
4. 因此一長串矩陣相乘，有不同的組合、括括號的方式，在最後一次相乘的各種方式中找出最小值，就可得到最快的方法，藉此可遞迴解決此問題。
   在每一種方式中，計算兩子問題的最快方法再加上最後一次相乘的時間，即可算出某種括號方式的最快時間。但直接遞迴需要用到 O(3^n) 的時間。使用動態規劃只需 O(n^3)。
5. 一個字串的 subsequence 是指由原字串剔除(沒有剔除也算在內)掉某些字元後剩下的字串，兩個字串的 longest common subsequence 是指兩個字串相同的子字串中最長的那些字串。
6. 兩個字串的字尾如果相同，那字尾一定在 LCS 之中，且 LCS 是兩個字串都剪掉字尾後的 LCS 再加上字尾。若是字尾不相同，那麼 LCS 要嘛不包含第一個字串的字尾，要嘛不包含第二個字串的字尾，利用此性質可得一遞迴解法，時間 O(2^(m+n))，使用動態規劃只需 O(mn)。
7. 電子字典中，每一個字被查詢的機率不同，每個錯字區間也是如此，希望設計出一個搜尋樹(最佳二元搜尋樹)，使得平均搜尋的時間最短，在一個搜尋樹中，搜尋時間的期望值即每個字或區間的機率乘上其所在的深度再相加，可以發現最佳搜尋樹的兩個子樹也要是最佳搜尋樹，而一棵樹的搜尋時間為整棵樹的機率加上兩個子樹的搜尋時間。藉此可得出一遞迴方法計算所有可能的搜尋樹得出最佳解。
   使用動態規劃，由只有一個元素的搜尋樹開始，計算搜尋時間，層層疊上計算出所有可能的子搜尋樹的最佳解，最後即可得完整的最佳搜尋樹。

貪婪演算法

1. 若某問題有以下兩種性質則可以使用貪婪演算法
1. 某些貪婪的選擇一定包含在最佳解之中
2. 做完選擇後的子問題仍會有 1. 的性質
2. 不像動態規劃將所有可能答案算出來早最佳解，貪婪演算法一個一個找出一定落在最佳解中的部分解，因此可以省下很多時間。
3. 活動規畫問題，每個活動有開始、結束時間，如何安排才可參加最多活動。可證明最先結束的活動一定落在某個最佳解之中，若最先結束的不再最佳解中，則將最佳解中最先結束的和所有活動最先結束的互換，不會造成任何牴觸，因此仍然是一個最佳解。而將最先結束的活動與與其牴觸的活動刪除後的子問題也會有此性質，因此可以此找到整個問題的最佳解，且花費時間只需 O(n)。
4. 偷東西問題，東西價值重量不同，而背包承重有限，如何取得最大價值的東西，若各物品可分割，則先拿價值密度最高的。
5. 不固定長度編碼法，若出現頻率較高的字元使用較短的編碼，則可省下許多空間，但為避免混淆，因此不同的編碼的字首必須不同，因此編碼可用一個二元搜尋樹表示，樹上兩條邊代表零或一，樹葉為被編碼的字元，依此由樹根走到樹葉就可得到一個編碼，因為抵達每個字元的路徑都不同，因此不會有編碼字首相同。
   可以證明某些最佳的編碼樹，出現機率最小的兩個字元會在離樹根最遠的地方，且共用一個父親。若有一個最佳編碼樹不是這樣，則把出現機率最小的那兩個和離樹根最遠共用父親的字元交換，交換後編碼樹的編碼長度期望值必定小於等於原本的狀況，因此得證。而且若將兩機率最小字元包起來，此子問題仍具有此性質。
   因此可得出貪婪演算法，將所有的字元丟入一個 min-heap  H 中，找出機率最小的兩個，將他們黏上同一個父親，再把其父親的機率設為兩小孩機率相加，將父親丟回 H 之中，遞迴可得最佳編碼樹。

amortize 分析

1. 在此分析的是，做一串運算所需的時間。
2. super stack，與一般的堆疊相同，只是多了一個功能：將堆疊中所有元素吐出來。在此堆疊做 n 次運算需要多少時間？將所有元素吐出來這個運算要花堆疊裡元素數量的時間，然而只做 n 次運算，堆疊裡最多只能有 n 個東西，且其他運算只需常數時間，因此時間複雜度為 O(n)，因此平均每一個運算只需常數時間，因此各種運算的 amortize cost 為 O(1) 。
3. 在一組運算中我們給每一個運算一個 amortize cost ，則使用這些 amortize cost 計算出來的總運算時間必須能夠壓過最糟糕的情況，不管各個運算的 cost 如何分配，分配負的 cost 也是可以，只要在混合運算時可以控制住情況即可，這是為了讓估計值更貼近實際值。
4. 計算 amortize cost 的方法：
1. 可以將做 n 次運算的實際 cost 算出來，在做分配；
2. 想像有一個 cost 銀行，你可以把某些運算的 cost 算多一點，多出來的存到銀行，或是存在某些物件身上，將來某些運算的 cost 就可以少算，只要證明這樣做不會造成分配的 cost 不夠用即可。
3. 為資料結構設計一個位能函數，把一個運算所改變的位能，加上它的實際 cost 算在他的 amortize cost 之中。
5. 動態表格，動態表格可以藉由重新找一個表格將原本表格上之資料複製過去的方法，依據狀態擴大或縮小表格，而達到節省空間的效果。而我們可以設計表格何時該增加何時該縮減，例如讓表格為承載全滿狀態，每增加或減少資料就更新一次表格，不過這樣花費許多時間： O(n^2)。
   因此我們以空間換取時間，資料全滿時表格變成兩倍，少於一半時表格減半，這樣表格至少會使用一半，我們令位能函數為超過一半的資料量的兩倍，如此一來當表格全滿時，位能就剛好可用來支付表格擴張，因此就不必分配 amortize cost 給表格擴張，而增加資料的運算會讓位能加二，因此 amortize cost = 3，增加資料這個運算的 amortize cost 就是 O(1)。
   然而當減少資料的運算也被考慮時，要是不斷重複擴張、縮小的動作，單一個運算就無法在 O(1) 的時間內完成，因此我們必須用更多空間來換取時間。
   讓表格在全滿時倍增，四分之一滿時減半，如此一來表格至少有四分之一滿，而此時的位能函數，當資料超過一半時一樣為倍增做準備，而當資料小於一半時則要為減半做準備，因此當資料小於一半時，減少資料的操作就要多算 1，而增加資料的運算就可以少算 1，如此一來所有運算便都是常數次

圖論

1. 圖可以用表格或是 list 儲存邊的資料。
2. 無向圖的表格對稱。
3. 表格轉置後每條邊的方向都會相反。
4. BFS：
   由圖中某一點出發，標記該點為已拜訪，先尋找離他最近的為找過的點，標記為以尋找，將這些點放入排隊中，由排隊中再找一點重複上述。
5. DFS：
   由一點出發，若有未拜訪鄰居就 DFS 他，遞迴下去直到有人沒有未拜訪的鄰居。
6. DFS 搜尋的路徑會形成一棵樹，而因為可能有些點不能由出發點到達，因此一個圖使用 DFS 會形成一座森林。
7. 一個點在 DFS 的結束時間為該點找不到未拜訪鄰居而回傳時，我們可以發現，經過 DFS 後在一個圖中的兩點，要嘛有直系血親關係要嘛沒有，若是有此關係，則祖先的開始結束時間會將後代的開始結束時間包含住；若是無此關係，則兩個點的開始結束時間將不會重疊。
8. 白色路徑定理，在 DFS 走到某點 v 時，另一點 u 與 v 有一條路徑相連，且全由未拜訪的點所構成，若且惟若在此 DFS 樹中， u 是 v 的子孫。
9. 四種邊：樹上的邊，子孫到祖先的邊，祖先到子孫的邊，沒有關聯的邊。
10. 無向圖上只有兩種邊：樹上的邊、子孫到祖先的邊。
11. 在一個有向圖上做 DFS ，若存在子孫到祖先的邊，若且惟若有 cycle。
12. Topological Sort
    有 cycle 的圖無法 Topological Sort
    將圖中各點 DFS 結束時間越晚的排越前面，可得Topological Sort。
13. 若圖中兩點各有一條路徑可通到對方，則稱此兩點互相可到達，此為一個等價關係，因此可以將圖做出一個分割(每一部分稱為SCC)，將每個 SCC 合併當成一個頂點，得到一個新的圖，且此圖中不會有任兩頂點互相可到達。
14. 一個圖將所有邊的方向相反，不會改變他的 SCC。
15. 對一個圖做 DFS，結束時間最晚的那個點必定落在沒有 income 的 SCC 之中， 因此若將所有的邊相反，這個 SCC 就沒有 outcome，對那個點使用 DFS 就可得該 SCC。